天天看點

c語言進階程式設計算法題

C語言進階程式設計算法題

    • 一、素數篩
    • 二、折半查找法
    • 三、矩陣翻轉

一、素數篩

輸入格式:輸入兩個正整數,分别為上述描述中的 N和 M,兩個正整數之間用一個空格分隔。

輸出格式:請按從小到大的順序輸出所有小于等于 N且大于等于 M 的質數,一個數單獨占一行。

樣例輸入1

5 3
           

樣例輸出1

3
5
           

樣例輸入2

30 5
           

樣例輸出2

5
7
11
13
17
19
23
29
           
#include <stdio.h>
#include <string.h>

int n = 1000000;
int mark[1000001];

int main() {
    int c;
    int j;
    int N;
    int M;
    memset(mark, 0, sizeof(mark));//對mark數組進行初始化為零
    mark[0] = 1;
    mark[1] = 1;
    scanf("%d%d",&N,&M);
    n = N;
    for (c = 2; c * c <= n; c++) {
            if(mark[c] != 1){
            for(j = 2; j <= n / c;j++){
                mark[c * j] = 1;
            }
        }
    }
    for(c =2;c <= n;c++){
        if(mark[c] != 1 && M<=c){
            printf("%d\n",c);
        }
    }
    return 0;
}
           

二、折半查找法

給定 N個整數和 K 個待查找的整數 M_1, M_2, …, M_KM 。如果待查找的整數在給定的 N個整數中,請輸出待查找的整數是數組中第幾個元素(從 1 開始計算,第一個元素計 1 而不是 0);如果待查找的整數不在給定的 N 個整數中,則輸出 0。

樣例輸入1

3 1
1 4 6
4
           

樣例輸出1

2
           

樣例輸入2

5 2
1 4 6 7 8
5 1
           

樣例輸出2

0 1
           

樣例輸入3

6 4
1 2 4 6 7 8 
9 1 5 2
           

樣例輸出3

0 1 0 2
           
#include <stdio.h>
int search(int *arr,int n,int m){
    int head = 0;
    int tail = n -1;
    int mid = 0;
    while(head <= tail){
        mid = (head + tail) >> 1;
        if(m == arr[mid]){
            return mid + 1;
        }
        if(m > arr[mid]){
            head = mid + 1;
        }
        if(m < arr[mid]){
            tail = mid -1;
        }
    }
    return 0;
}
int main() {
    int n;
    int k;
    int numbers[1000001];
    int m;
    int i;
    int j;
    int res;
    while (scanf("%d%d", &n, &k) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%d", &numbers[i]);
        }
        for (j = 0; j < k; j++) {
            scanf("%d", &m);
            res = search(numbers,n,m);
            printf("%d",res);
            if(j < k -1)
            {
                printf(" ");
            }
        }
    }
    return 0;
}
           

三、矩陣翻轉

輸入第一行包括由空格分開的整數M、N、T(0 < M < 200,0 < N < 200,T=0或1),其中M和N分别表示待處理矩陣的行數與列數,T為0時表示左右翻轉,為1時表示上下翻轉。之後的M行,每行包括由空格分隔的N個整數,依次為輸入矩陣的每一行的資料。

輸出包括M行N列,每個數字之間用一個空格分隔,每一行行末均有一個空格,表示的是按照要求翻轉後的矩陣。

樣例輸入

4 4 1
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
           

樣例輸出

3 4 5 6 
9 0 1 2 
5 6 7 8 
1 2 3 4 
           

這算是一道比較典型的大化小的問題,要對整個矩陣進行上下左右翻轉,并且僅僅是上下翻轉一次或左右翻轉一次。隻要關注每一行或列的翻轉,因為操作都是一樣的。

代碼如下:

#include<stdio.h>
int main(void){
int m, n, t;
int i, j, k;
int a[200][200];
scanf("%d%d%d", &m, &n, &t);
if(m < 1 || m > 199 || n < 1 || n > 199)
return 0;
if(t != 0 && t != 1)
return 0;
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
scanf("%d", &a[i][j]);

if(t == 0){
	for(j = 0; j < m; j++){
		for(i = 0; i < n/2; i++){
			k = a[j][i];
			a[j][i] = a[j][n-i-1];
			a[j][n-i-1] = k;
		}
	}
for(i = 0; i < m; i++){
	for(j = 0; j < n; j++){
		printf("%d ", a[i][j]);
		printf("\n");
		}
	}
}
else {
		for(j = 0; j < n; j++){
			for(i = 0; i < m/2; i++){
				k = a[i][j];
				a[i][j] = a[m-i-1][j];
				a[m-i-1][j] = k;
		}
	}
for(i = 0; i < m; i++){
		for(j = 0; j < n; j++){
			printf("%d ", a[i][j]);
			printf("\n");
		}
	}
}
return 0;
}