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;
}