算法练习题（一）
1.题型：数组与字符串
例一：生成元问题
题目：如果x+x的各个数字之和得到y，就是说x是y的生成元。给出n（1<=n<=100000),求最小生成元。无解输出0.例如，n=216,121,2005时的解分别是198,0,1979。
解题思路：枚举100000内的所有正整数m，标记“m加上m的各个数字之和得到的数有一个生成元是m”，最后查表即可。（打表法）
代码：
#include#include #define maxn 100005int ans[maxn];int main() {int T, n;memset(ans, 0, sizeof(ans));int m;for (m = 1; m < maxn; m++) { int x = m, y = m; while(x > 0) { y += x % 10; x /= 10; } if (ans[y] == 0 || m < ans[y]) ans[y] = m; // 疑问：ans[y]的值来源于m，m为累加数，m
#注：本题目及代码源于刘汝佳 著《算法竞赛 入门经典》第二版。
例二：环状序列问题
题目：长度为n的环状串有n种表示方法，分别为从某个位置开始顺时针得到，在这些排列中字典顺序最小的称“最小表示”。如CTCC的最小表示为CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。
解题思路：对于两个字符串，从第一的字符开始比较，当某一个位置的字符不同时，该位置字符较小的串，字典序小。如果一个字符串没有更多的字符，但另一个字符串还没结束，则较短的字符串的字典序较小。其实就是定义两个int变量并分别记录数组的下标，一个用于循环，一个用于记录当前开始最小的字符串的下标。
代码：
#include#include #define maxn 105// 环状串s的表示法p是否比表示法q的字典序小 int less (const char* s, int p, int q) { int n = strlen(s); int i; for (i = 0; i < n; i++) if (s[(p+i) % n] != s[(q+i) % n]) return s[(p+i) % n] < s[(q+i) % n]; return 0; // 相等 } int main() { int T; char s[maxn]; scanf("%d", &T); // 输入要检测序列数 while (T--) { scanf("%s", s); int ans = 0; int n = strlen(s); int i; for (i = 1; i < n; i++) if (less(s, i, ans)) ans = i; for (i = 0; i < n; i++) putchar(s[(i+ans) % n]); putchar('\n'); } return 0;}
#注：本题目及代码源于刘汝佳 著《算法竞赛 入门经典》第二版。
从现在开始每周写博客，立此为据！！！ （2017/03/04）
附：诗
偶然
----徐志摩
我是天空里的一片云，
偶尔投影在你的波心－－ 你不必讶异， 更无须欢喜－－ 在转瞬间消灭了踪影。你我相逢在黑夜的海上，
你有你的，我有我的，方向； 你记得也好， 最好你忘掉， 在这交会时互放的光亮！