1.有序序列判断
描述
输入一个整数序列，判断是否是有序序列，有序，指序列中的整数从小到大排序或者从大到小排序(相同元素也视为有序)。
输入描述：
第一行输入一个整数N(3≤N≤50)。
第二行输入N个整数，用空格分隔N个整数。
输出描述：
输出为一行，如果序列有序输出sorted，否则输出unsorted。
这道题目不难，不过怎么优化是关键。笔者刚开始写的时候比较笨，写的很复杂，做了两个冒泡排序，一个顺序，一个逆序，然后和输入的数组进行比较，简直太笨了。
①.暴力解法(笨笨的)
#include<stdio.h> void bubble_sort1(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int flag = 1; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 0; } } if (flag == 1) break; } } void bubble_sort2(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int flag = 1; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] < arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 0; } } if (flag == 1) break; } } int main() { int n, j; int arr1[50] = { 0 }; int arr2[50] = { 0 }; int arr3[50] = { 0 }; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &arr1[i]); arr2[i] = arr1[i]; arr3[i] = arr1[i]; } bubble_sort1(arr2, n); bubble_sort2(arr3, n); for (j = 0; j < n; j++) { if ((arr1[j] != arr2[j]) && (arr1[j] != arr3[j])) break; } if (j == n) { printf("sorted\n"); } else printf("unsorted\n"); return 0; }
②.优化算法
如果换个角度看问题呢？其实我们只是需要两个计数器，一个计算顺序，一个计算逆序，然后再进行比较即可。这个法式真的便捷
上代码：
#include<stdio.h> int main() { int n,j; int count1=0;//计算升序 int count2=0;//计算降序 int arr[50]={0}; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&arr[i]); } for(int j=0;j<n-1;j++) { //升序 if(arr[j]<arr[j+1]) count2++; else count1++; } if(count1==n-1||count2==n-1) { printf("sorted\n"); } else printf("unsorted\n"); return 0; }
代码量真的大大减少。可见每个问题都要多角度进行思考，算法才能更加简便。
结果：
2.扫雷
扫雷矩阵的每一行每一列都是一个数字，每个数字的含义是与当前位置相邻的8个方向中，有多少个雷（在下图中，雷用*表示）；如果当前位置就是雷的话，仍输出一个*。
输入描述：
第一行两个整数n,m，代表矩阵有n行m列
接下来共n行，每行m个字符
输出描述：
输出共n行m列，为扫雷矩阵。
输入：
4 4
....
..**
*.*.
.*.*
输出：
0122
13**
*4*4
2*3*
这道题目也是不难的，不过笔者思维受之前做的小游戏的限制，一直想把'.'换成'0',把'*'换成'1'。这样计数就会极其方便，但是笔者越写越不对劲，因为我是对每个坐标进行运算后更改成数表示它的周围有几个雷，然后就出现了bug，更改后之后运算的数就会受到影响，因为后面的数进行运算会把这个数也算上，就会导致重复运算。
其实没必要这么麻烦，只需要判断是不是*就够了，设个计数器，就可以了，（这么简单的事情博主真够笨的😂）。不过这道题目比较坑的在于scanf的问题，因为输入的比如说空格了，回车了，都会被scanf吸走当成数组的值，那么就会出现bug，所以需要getchar()掉，几个getchar的放置需要格外小心。
上代码：
#include <stdio.h> int num(int i,int j,char str[1002][1002]) { int count =0; int r,c; for (r = i - 1; r <= i + 1; r++) { for (c = j - 1; c <= j + 1; c++) { if (str[r][c] == '*') count++; } } return count; } int main() { int i=0; int j=0; int n=0; int m=0; int ret=0; char str[1002][1002]={0}; scanf("%d %d",&n,&m); getchar();//两个数之后的回车getchar掉 for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%c",&str[i][j]); } getchar();//换行getchar掉 } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(str[i][j]!='*') { ret=num(i,j,str); str[i][j]=ret+'0'; } } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%c",str[i][j]); } printf("\n"); } return 0; }
结果：
正确。
3.笨小猴记单词
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
输入描述：
只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
输出描述：
共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。
这道题目让我也很是头痛，一直想不到一个好的方法去统计字母出现的次数，然后也是请教的大佬，学到了一种新颖又方便的方式。
新建一个数组，有相同名字的数组所对应的值加一。真的很厉害。
#include<stdio.h> #include<string.h> #include<math.h> int main() { char word[100]={0}; int arr[100]={0}; //这个思路很厉害，新建一个数组，有相同名字的数组所对应的值加一 scanf("%s",&word); getchar(); int maxn,minn,i,j; for(i=0;i<strlen(word);i++) { arr[word[i]-'0']++; } maxn=0; minn=100; for(j=0;j<100;j++) { if(maxn<arr[j]) maxn=arr[j]; if(arr[j]!=0&&minn>arr[j]) minn=arr[j]; } int tmp=maxn-minn; int flag=1; if(tmp==1||tmp==0) { flag=0; } else { for(i=2;i<=sqrt(tmp);i++)//对于1和0要额外判断，因为这个循环不包括1和0 { if(tmp%i==0) { flag=0; break; } } } if(flag==0) { printf("No Answer\n"); printf("0\n"); } else { printf("Lucky Word\n"); printf("%d\n",tmp); } return 0; }
结果：
4.添加逗号
描述
对于一个较大的整数 N(1<=N<=2,000,000,000)
比如 980364535，我们常常需要一位一位数这个数字是几位数，但是如果在这 个数字每三位加一个逗号，它会变得更加易于朗读。
因此，这个数字加上逗号成如下的模样：980,364,535请写一个程序帮她完成这件事情
输入描述：
一行一个整数 N
输出描述：
一行一个字符串表示添加完逗号的结果
输入：
980364535
输出：
980,364,535
笔者在这个问题上又钻了死胡同，一直想着新建一个数组把原来的数分割，再加上逗号存起来，但是，真的好难实现。其实后来一想，没必要只要碰到就直接打印出来逗号就可以了。
#include<stdio.h> //别一直想把它存到数组里，直接打印出来就行了 int main() { char arr[21]="0"; scanf("%s",&arr); //倒着计数 int i=20; while(arr[i]=='\000') { i--; } for(int j=0;j<=i;j++) { printf("%c",arr[j]); if((i-j)%3==0&&i!=j) printf(","); } return 0; }
结果：
5.回文数
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个N（2<=N<=10或N=16）进制数M（100位之内），求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
进制N>10时，使用大写'A'字母表示10，'B'表示11,...,'E'表示16
输入描述：
两行，分别为N,M
输出描述：
STEP=ans
输入：
9
87
输出：
STEP=6
这道题目，笔者在第一次解答时，仅仅由于是用scanf吸收整型，导致仅能解决10进制以内的回文数判断。但是这是16进制内的，所以仅能利用字符串来解决。这道题目，笔者写起来比较困难，自己也比较笨。仅仅是用暴力解法解答，有更优化的算法欢迎大佬指教。
暴力解法：
void transform(char ch1[100],int ch_1[100],int i) { for (int j = 0; j <= i; j++) { switch (ch1[j]) { case 'A': ch_1[j] = 10; break; case 'B': ch_1[j] = 11; break; case 'C': ch_1[j] = 12; break; case 'D': ch_1[j] = 13; break; case 'E': ch_1[j] = 14; break; case 'F': ch_1[j] = 15; break; default: ch_1[j] = ch1[j] - '0'; break; } } } int Add(char ch1[100], char ch2[100],char sum[100],int i,int n) { //对数组进行变换，由char型变为int型 int ch_1[100] = { 0 }; int ch_2[100] = { 0 }; transform(ch1, ch_1, i); transform(ch2, ch_2, i); int j = 0; while (i>=0) { int tmp = ch_1[j] + ch_2[j]; if (tmp < n&&n>10) { switch (tmp) { case 10: sum[j] = 'A'; break; case 11: sum[j] = 'B'; break; case 12: sum[j] = 'C'; break; case 13: sum[j] = 'D'; break; case 14: sum[j] = 'E'; break; case 15: sum[j] = 'F'; break; default: sum[j] = tmp + '0'; break; } } else if (tmp<n&&n<=10) { sum[j] = tmp + '0'; } else if (tmp >= n && n > 10) { ch_1[j + 1] += 1; switch (tmp%n) { case 10: sum[j] = 'A'; break; case 11: sum[j] = 'B'; break; case 12: sum[j] = 'C'; break; case 13: sum[j] = 'D'; break; case 14: sum[j] = 'E'; break; case 15: sum[j] = 'F'; break; default: sum[j] = tmp%n + '0'; break; } } else if (tmp >= n && n <= 10) { ch_1[j + 1] += 1; sum[j] = tmp % n+'0'; } i--; j++; } if (ch_1[j] > 0) sum[j] = ch_1[j] + '0'; else j = j - 1; //再颠倒 int left = 0; int right = j; while (left <= right) { char ret = sum[left]; sum[left] = sum[right]; sum[right] = ret; left++; right--; } return j; } int is_pan(char sum[100],int j) { int left = 0; int right = j; while (left <= right) { if (sum[left] != sum[right]) return 0; left++; right--; } return 1; } int main() { //搞明白自己的错误点，逆序和进制没有关系，不能把所有的数转化为10进制再运算。 //由于有16等进制的存在，所以要获取字符，而不是数字 int n; char ch1[100] = { 0 }; char ch2[100] = { 0 }; int i = 0; int count = 1; scanf("%d", &n); getchar(); while (scanf("%c", &ch1[i])!=EOF) { if (ch1[i] == '\n') break; i++; } i = i - 1; //逆序，逆序之后再做进制运算 //用一个新数组存 while (1) { char sum[100] = { 0 }; int j = 0; int tmp = i; for (j = 0; j <= i; j++) { ch2[j] = ch1[tmp]; tmp--; } int ret = Add(ch1, ch2, sum, i, n); //已经得到sum[]; int out = is_pan(sum, ret); if (out == 1) { printf("STEP=%d\n", count); break; } else { i = ret; for (j = 0; j <= ret; j++) { ch1[j] = sum[j]; } count++; if (count > 30) { printf("Impossible!\n"); break; } continue; } } return 0; }
真的离谱写了这么多。
还好对了。/(ㄒoㄒ)/~~
6.数组匹配
牛牛刚学会数组不久，他拿到两个数组 a 和 b，询问 b 的哪一段连续子数组之和与数组 a 之和最接近。
如果有多个子数组之和同样接近，输出起始点最靠左的数组。
输入描述：
第一行输入两个正整数 n 和 m ，表示数组 a 和 b 的长度。
第二第三行输入 n 个和 m 个正整数，表示数组中 a 和 b 的值。
输出描述：
输出子数组之和最接近 a 的子数组
输入：
2 6
30 39
15 29 42 1 44 1
输出：
29 42
这道题目也是暴力解法。便利所有目标数组。
#include <stdio.h> int num(int x,int y) { if(x>=y) return x-y; else return x-y; } int main() { int n,m; scanf("%d %d",&n,&m); int a[100]={0}; int b[100]={0}; int sum1=0,sum2=0,min,k,l; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } for(int i=0;i<m;i++) { scanf("%d",&b[i]); } for(int i=0;i<n;i++) { sum1+=a[i]; } min=sum1; for(int i=0;i<m;i++) { sum2=b[i]; for(int j=i+1;j<=m;j++) { if(num(sum1,sum2)<min) { min=num(sum1,sum2); k=i; l=j; } sum2+=b[j]; } } for(int i=k;i<l;i++) { printf("%d ",b[i]); } return 0; }
