《 算法竞赛入门经典》课后题解，第二发来袭。
习题2-1 位数（digit）
#include <stdio.h>int main(){int n,digit;while(~scanf("%d",&n)){digit = 0;if(n==0)digit = 1;while(n>0){n /= 10;digit++;}printf("%d\n",digit);}return 0;}
习题2-2 水仙花数（daffodil）
这是一个很经典的问题，对于本题数据量比较小，，所以我们直接使用暴力求解
#include <stdio.h>int main(){int p1,p2,p3,i;for( i = 100; i < 1000; i++){p1 = i/100;p2 = (i – 100*p1)/10;p3 = i%10;if( i == p1*p1*p1 + p2*p2*p2 + p3*p3*p3 )printf("%d ",i);}return 0;}
习题2-3 韩信点兵（hanxin）背景故事
果断暴力求解：
#include <stdio.h>int main(){int i,a,b,c;//a,b,c分别是3人一排，5人一排，7人一排的剩余人数while(~scanf("%d%d%d",&a,&b,&c)){for(i = 10; i <= 100; i++){//暴力求解if(i%3==a&&i%5==b&&i%7==c){printf("%d\n",i);break;}}if(i>100)printf("No answer\n");}return 0;}
习题2-4 倒三角形（triangle）
这一题属于字符串处理的题目，本题需要特别注意的地方就是倒三角右侧的空白与左侧空白的区别，这个弄明白这类的题目通常都差不多
#include <stdio.h>int main(){int n,p1,p2,i,j,k;//其中p1代表#的个数，p2代表空格的个数while(~scanf("%d",&n)){p1 = 2*n -1;p2 = 0;for( i = 0; i < n; i++){for( j = 0; j < p2; j++)printf(" ");for( k = 0; k < p1; k++)printf("#");printf("\n");p2++;p1-=2;}}return 0;}
习题2-5 统计（stat）
#include <stdio.h>#include <stdlib.h>int main(){int n,m,i,cnt; //cnt为计数器，用于记录大于m的数的个数while(scanf("%d",&n)){int *a = (int*)malloc(sizeof(int)*n); //动态申请内存cnt = 0;//计数器初始化for( i = 0; i < n; i++ )scanf("%d",&a[i]);scanf("%d",&m);for( i = 0; i < n; i++ ){if( a[i] < m )cnt++;}printf("%d\n",cnt);free(a);a = NULL;}return 0;}
重定向版：
#define LOCAL#include <stdio.h>#include <stdlib.h>int main(){#ifdef LOCALfreopen("data.in","r",stdin);freopen("data.out","w",stdout);#endif//后面一样}
fopen版：
#include <stdio.h>#include <stdlib.h>int main(){FILE* fin,*fout;fin = fopen("data.in","rb");fout = fopen("data.out","wb");int n,m,i,cnt; //cnt为计数器，用于记录大于m的数的个数while(fscanf(fin,"%d",&n)==1){int *a = (int*)malloc(sizeof(int)*n); //动态申请内存cnt = 0;//计数器初始化for( i = 0; i < n; i++ )fscanf(fin,"%d",&a[i]);fscanf(fin,"%d",&m);for( i = 0; i < n; i++ ){if( a[i] < m )cnt++;}fprintf(fout,"%d\n",cnt);free(a);a = NULL;}fclose(fin);fclose(fout);return 0;}
就方便而言个人认为重定向的方法比较简便
习题2-6 调和级数（harmony）
#include <stdio.h>double Slove(int n){int i;double f = 0;for( i = 1; i <= n; i++ )f += 1.0/i;return f;}int main(){int n;while(scanf("%d",&n))printf("%.3lf\n",Slove(n));return 0;}
习题2-7 近似计算（approximation）
#include <stdio.h>int main(){int i,p = 1;double sum,temp_i;for( i = 1;;i++){temp_i = 1.0/i;sum += p*temp_i;p = -p;if(temp_i < 10e-6)break;}printf("%lf\n",4*sum);return 0;}
习题2-8 子序列的和（subsequence）
本题的陷阱是当n过大时，会造成 n*n溢出
#include <stdio.h>int main(){int n,m,i;double sum;while(scanf("%d%d",&n,&m)){sum = 0;for( i = n; i <= m; i++ )sum += 1.0/i*1.0/i;printf("%.5lf\n",sum);}return 0;}
习题2-9 分数化小数 （decimal）
这一题，使用借位的方法就可顺利解决，同时需要采用模拟数组的方法
#include <stdio.h>#include <stdlib.h>int digit(int n){int cnt = 0;while(n>0){n/=10;cnt++;}return cnt;}int main(){int a,b,c,n,dgt,temp,i,k;//a,b,c如题意所示,n表示a/b的整数部分，dgt表示n的位数char *p;while(scanf("%d%d%d",&a,&b,&c)){i = 0;n = a/b;if( n < 1){dgt = 1;p = (char*)malloc(sizeof(char)*(c+10));p[i++] = '0';p[i++] = '.';}else{dgt = digit(n);a = a – n*b;p = (char*)malloc(sizeof(char)*(dgt+c+10));i = dgt,k = dgt;while(k>0){p[–k] ='0' + n%10;n /= 10;}p[i++] = '.';}while(i<=c+dgt+1){a *= 10;temp = a / b;a %= b;p[i++] = temp + '0';}if(p[i-1]>='5')p[i-2] = p[i-3] + 1;p[i-1] = '\0';puts(p);free(p);p =NULL;}return 0;}
习题2-10 排列（permutation）
#include <stdio.h>int main(){int a,b,c,num[10]={0},i,tmp;for(a = 100; a < 333; a++ ){ //因为 c <1000 => a <333b = 2 * a, c = 3 * a;//将使用过的数字进行标记num[a/100] = num[a/10%10] = num[a%10] = 1;num[b/100] = num[b/10%10] = num[b%10] = 1;num[c/100] = num[c/10%10] = num[c%10] = 1;i = 1,tmp = 0;while(i<10)tmp += num[i++];if( tmp == 9 ) //将使用过的数字进行统计printf("%d %d %d\n",a,b,c);for(i = 1; i < 10; i++) //将数字的标记擦除num[i] = 0;}return 0;}
问候不一定要慎重其事，但一定要真诚感人
