1. 質數判斷
對於這個，很多人可能會直接這樣寫：
view plaincopy to clipboardprint?int isPrime(int n) //函數返回1表示是質數，返回0表示不是質數
{
int i;
for (i = 2; i < n; i++)
if (n % i == 0)
break;
return i >= n;
}
int isPrime(int n) //函數返回1表示是質數，返回0表示不是質數
{
int i;
for (i = 2; i < n; i++)
if (n % i == 0)
break;
return i >= n;
}
又或者，有的人知道平方根的優化：
view plaincopy to clipboardprint?int isPrime(int n)
{
int i, s = (int)(sqrt((double)n) + 0.01);
for (i = 2; i <= s; i++)
if (n % i == 0)
break;
return i > s;
}
int isPrime(int n)
{
int i, s = (int)(sqrt((double)n) + 0.01);
for (i = 2; i <= s; i++)
if (n % i == 0)
break;
return i > s;
}
再或者，消除偶數：
view plaincopy to clipboardprint?int isPrime(int n)
{
int i, s = (int)(sqrt((double)n) + 0.01);
if (n <= 3) return 1;
if (n % 2 == 0) return 0;
for (i = 3; i <= s; i += 2)
if (n % i == 0)
break;
return i > s;
}
int isPrime(int n)
{
int i, s = (int)(sqrt((double)n) + 0.01);
if (n <= 3) return 1;
if (n % 2 == 0) return 0;
for (i = 3; i <= s; i += 2)
if (n % i == 0)
break;
return i > s;
}
當然，這樣還不是很夠的話，我們可以考慮這個事實：
所有大於4的質數，被6除的余數只能是1或者5
比如接下來的5,7,11,13,17,19都滿足
所以，我們可以特殊化先判斷2和3
但後面的問題就出現了，因為並非簡單的遞增，從5開始是+2,+4,+2,+4,....這樣遞增的
這樣的話，循環應該怎麼寫呢？
首先，我們定義一個步長變量step，循環大概是這樣 for (i = 5; i <= s; i += step)
那麼，就是每次循環，讓step從2變4，或者從4變2
於是，可以這麼寫：
view plaincopy to clipboardprint?#include <stdio.h>
#include <math.h>
int isPrime(int n)
{
int i, s = (int)(sqrt((double)n) + 0.01), step = 4;
if (n <= 3) return 1;
if (n % 2 == 0) return 0;
if (n % 3 == 0) return 0;
for (i = 5; i <= s; i += step)
{
if (n % i == 0)
break;
step ^= 6;
}
return i > s;
}
int main()
{
int n;
for (n = 2; n < 100; ++n) //找出 2 - 100 的質數並輸出
{
if (isPrime(n)) printf("%d,", n);
}
getchar();
return 0;
}
#include <stdio.h>
#include <math.h>
int isPrime(int n)
{
int i, s = (int)(sqrt((double)n) + 0.01), step = 4;
if (n <= 3) return 1;
if (n % 2 == 0) return 0;
if (n % 3 == 0) return 0;
for (i = 5; i <= s; i += step)
{
if (n % i == 0)
break;
step ^= 6;
}
return i > s;
}
int main()
{
int n;
for (n = 2; n < 100; ++n) //找出 2 - 100 的質數並輸出
{
if (isPrime(n)) printf("%d,", n);
}
getchar();
return 0;
}
如上代碼，一個 step ^= 6; 完成step在2和4之間轉換（這個 ^ 符號是C裡的異或運算）
理由是，2化二進制是010，4是100，6是110，於是2異或4得到6：
2 ^ 4 => 6
6 ^ 2 => 4
6 ^ 4 => 2
於是利用異或，就可以構造這種步長在兩個值之間來回變化的循環
思考題：前面說的是雙值循環，那麼如何構造三值或者四值循環？
2.菱形打印
很多人，打印菱形在控制台的思路是，把菱形上下拆分，分兩段很接近的代碼來打印，
其實這樣代碼很不好看，並且不好閱讀
我們知道，要打印的圖案是這種：
*
***
*****
***
*
滿足上下對稱，左右對稱，那麼，你能不能也弄一個二重循環，同樣是對稱的？
很簡單，首先我們要拋開習慣性思維，for循環不一定要在0開始或者0結束
我們可以讓循環從 -c 到 c ，這樣不就輕松產生一個對稱的嗎？（只要取個絕對值）
我們把菱形的中心看成是坐標0,0，那麼，會輸出星號的坐標，是 |x| + |y| <= c 的點
由此可得
view plaincopy to clipboardprint?#include <stdio.h>
#define IABS(x) ( (x) >= 0 ? (x) : -(x) ) //定義一個計算絕對值的宏
void print(int size) // size是這個菱形的半徑，直徑會是size * 2 + 1
{
int x, y;
for (y = -size; y <= size; y++)
{
for (x = -size; x <= size; x++)
{
if ( IABS(x) + IABS(y) <= size ) //x和y各自的絕對值的和，即 |x| + |y| <= size
putchar('*');
else
putchar(' ');
}
putchar('\n');
}
}
int main()
{
print(5); //輸出一個半徑為5的菱形
getchar();
return 0;
}
#include <stdio.h>
#define IABS(x) ( (x) >= 0 ? (x) : -(x) ) //定義一個計算絕對值的宏
void print(int size) // size是這個菱形的半徑，直徑會是size * 2 + 1
{
int x, y;
for (y = -size; y <= size; y++)
{
for (x = -size; x <= size; x++)
{
if ( IABS(x) + IABS(y) <= size ) //x和y各自的絕對值的和，即 |x| + |y| <= size
putchar('*');
else
putchar(' ');
}
putchar('\n');
}
}
int main()
{
print(5); //輸出一個半徑為5的菱形
getchar();
return 0;
}
如果我需要得到空心菱形呢？非常非常簡單，因為菱形邊界上的點，滿足的是|x| + |y| == c
所以，我們只要把那個if裡的小於等於號，改成雙等於號 == 就可以了
再類似地，如果我不要*號，我要最外層是字母A，然後裡一層是B這樣呢？即：
A
ABA
ABCBA
ABA
A
那麼，我們只要在putchar那裡做一個字符計算：
view plaincopy to clipboardprint?void print(int size) // size是這個菱形的半徑，直徑會是size * 2 + 1
{
int x, y;
for (y = -size; y <= size; y++)
{
for (x = -size; x <= size; x++)
{
if ( IABS(x) + IABS(y) <= size ) //x和y各自的絕對值的和，即 |x| + |y| <= size
putchar( 'A' + (size - IABS(x) - IABS(y)) ); //留意這裡的計算方法
else
putchar(' ');
}
putchar('\n');
}
}
void print(int size) // size是這個菱形的半徑，直徑會是size * 2 + 1
{
int x, y;
for (y = -size; y <= size; y++)
{
for (x = -size; x <= size; x++)
{
if ( IABS(x) + IABS(y) <= size ) //x和y各自的絕對值的和，即 |x| + |y| <= size
putchar( 'A' + (size - IABS(x) - IABS(y)) ); //留意這裡的計算方法
else
putchar(' ');
}
putchar('\n');
}
}
類似地，如果我們要打印的是X形：
* *
* *
*
* *
* *
同樣可以利用這個思路完成，這題就作為思考題吧
3. 奇數階幻方
所謂幻方（最基本的那種），就是橫，豎，對角線上的數的和等於一個常數的數字方陣
4 3 8
9 5 1
2 7 6
以上這個圖，有什麼規律？容易寫成代碼嗎？
我們把這個圖，向右復制五次，向下復制三次，展開一下：
4 3 8 4 3 8 4 3 8 4 3 8 4 3 8
9 5 1 9 5 1 9 5 1 9 5 1 9 5 1
2 7 6 2 7 6 2 7 6 2 7 6 2 7 6
4 3 8 4 3 8 4 3 8 4 3 8 4 3 8
9 5 1 9 5 1 9 5 1 9 5 1 9 5 1
2 7 6 2 7 6 2 7 6 2 7 6 2 7 6
4 3 8 4 3 8 4 3 8 4 3 8 4 3 8
9 5 1 9 5 1 9 5 1 9 5 1 9 5 1
2 7 6 2 7 6 2 7 6 2 7 6 2 7 6
注意藍色數字的走向
怎麼樣，現在呢？
現在看起來顯得規律性強了很多，但是，你會不會覺得循環還是不太好寫？
我們如何從一個給定的n，直接得知它的坐標呢？
不難，找一下規律就可以發現對於任意的數值n+1有（以左上角為0,0坐標）：
x = 2 + n + n / 3;
y = 1 + n - n / 3;
其實這個規律可以簡單擴展到任意奇數階幻方（以下size是奇數）：
x = size / 2 + 1 + n + n / size; (注意這裡的除法是取整除法，不帶小數)
y = size / 2 + n - n / size;
這樣，我們就可以把原來復雜的循環，化簡成一重簡單循環
於是有程序：
view plaincopy to clipboardprint?#include <stdio.h>
#define SIZE 5 //定義幻方階數，這個數只能是奇數
int main()
{
int x, y, i, sqSize, hSize;
int sqMap[SIZE][SIZE];
sqSize = SIZE * SIZE;
hSize = SIZE / 2;
//計算1至SIZE * SIZE的數的位置並記錄
for ( i = 0; i < sqSize; i++)
{
x = hSize + 1 + i + i / SIZE;
y = hSize + i - i / SIZE;
sqMap[y % SIZE][x % SIZE] = i + 1;
}
//以下是輸出
for (y = 0; y < SIZE; y++)
{
for (x = 0; x < SIZE; x++)
printf("%4d", sqMap[y][x]);
puts("");
}
return 0;
}
#include <stdio.h>
#define SIZE 5 //定義幻方階數，這個數只能是奇數
int main()
{
int x, y, i, sqSize, hSize;
int sqMap[SIZE][SIZE];
sqSize = SIZE * SIZE;
hSize = SIZE / 2;
//計算1至SIZE * SIZE的數的位置並記錄
for ( i = 0; i < sqSize; i++)
{
x = hSize + 1 + i + i / SIZE;
y = hSize + i - i / SIZE;
sqMap[y % SIZE][x % SIZE] = i + 1;
}
//以下是輸出
for (y = 0; y < SIZE; y++)
{
for (x = 0; x < SIZE; x++)
printf("%4d", sqMap[y][x]);
puts("");
}
return 0;
}
這個比你網上能找到的很多求奇數階幻方的代碼都短小很多（不過網上較多稱之為魔方陣，不知為何）
4. 字符串循環移位
問題，給你一個字符串，要求循環左移n位
比如對"abcdefg" 循環左移2位，我們要得到"cdefgab"
附加條件，不能使用連續輔助空間（包括動態分配），只能使用若干單個變量（即O(1)空間）
首先，我們知道，反轉一個字符串操作（"abcd"變"dcba"），是不需要額外數組輔助的，只要頭尾數據交換就可以了
然而，可能你不知道，僅僅使用字符串反轉可以實現字符串循環移位：
view plaincopy to clipboardprint?//反轉字符串，把st與ed所指向的中間的內容反轉（包含st不包含ed）
void str_rev(char* st, char *ed)
{
for (--ed; st < ed; ++st, --ed)
{
char c;
c = *st; *st = *ed; *ed = c;
}
}
//反轉字符串，把st與ed所指向的中間的內容反轉（包含st不包含ed）
void str_rev(char* st, char *ed)
{
for (--ed; st < ed; ++st, --ed)
{
char c;
c = *st; *st = *ed; *ed = c;
}
}
view plaincopy to clipboardprint?//用三反轉等效左移字符串（st與ed之間，包含st不包含ed的內容）
char* str_shl(char* st, char* ed, int n)
{
str_rev(st, &st[n]);
str_rev( &st[n], ed);
str_rev(st, ed);
return st;
}
//用三反轉等效左移字符串（st與ed之間，包含st不包含ed的內容）
char* str_shl(char* st, char* ed, int n)
{
str_rev(st, &st[n]);
str_rev( &st[n], ed);
str_rev(st, ed);
return st;
}
view plaincopy to clipboardprint?#include <stdio.h>
#include <string.h>
int main()
{
char str[] = "abcdefghijklmnopqrstuvwxyz";
puts( str_shl(str, str + strlen(str), 6) );
getchar();
return 0;
}
#include <stdio.h>
#include <string.h>
int main()
{
char str[] = "abcdefghijklmnopqrstuvwxyz";
puts( str_shl(str, str + strlen(str), 6) );
getchar();
return 0;
}
這裡，如果要循環左移n位，只要把原來字符串分成兩段，前n字符，和後面其它字符
兩段分別反轉，最後再整體反轉，就實現了循環左移（如果先整體再兩部分，就是循環右移）
作者“Csdn_zc的專欄”
