首页 > 分享 > 算法竞赛入门经典笔记—第二章

算法竞赛入门经典笔记—第二章

花匠小妙招
2024-09-16 23:04

例2-1： 输出所有形如aabb的4位完全平方数（即前两位数字相等，后两位数字也相等）。
编写程序时，尽量缩小变量定义的范围。
将伪代码改为代码时，一般先选择较为容易的部分进行。

#include <stdio.h> #include <math.h> int main() { for(int a=0;a<=9;a++){ for(int b=0;b<=9;b++){ int n = a*1100+b*11; int t = floor(sqrt(n+0.5));//函数floor(x)返回值为不超过x的最大整数 if((t*t==n)&&(n>0)) printf("%dn",n); } } return 0; } 1234567891011121314

int 的范围是 − 2 31 -2^{31} −231~ 2 31 − 1 2^{31} -1 231−1

long long int 范围是 − 2 63 -2^{63} −263~ 2 63 − 1 2^{63} -1 263−1，要把输入时的％d改成％lld。在MinGW的gcc中，要把％lld改成％I64d，涉及long long的输入输出，常用C＋＋的输入输出流或者自定义的输入输出方法。

可以使用time.h和clock（）函数获得程序运行时间。常数CLOCKS_PER_SEC和操作系统相关，不要直接使用clock（）的返回值，而应总是除以CLOCKS_PER_SEC。

例题2-4: 输入n，计算S＝1！＋2！＋3！＋…＋n！的末6位(不含前导0).n≤106，n！表示前n个正整数之积。

#include<stdio.h> #include<time.h> int main() { const int MOD = 1000000; int n, S = 0; scanf("%d", &n); if(n>25)//25!末尾有6个0n=25; for(int i = 1; i <= n; i++) { int factorial = 1; for(int j = 1; j <= i; j++) factorial = (factorial * j % MOD); S = (S + factorial) % MOD; } printf("%dn", S); printf("Time used = %.2fn", (double)clock() / CLOCKS_PER_SEC); return 0; }

123456789101112131415161718192021

管道技巧：终端中使用echo 20|文件名，可以将20作为输入运行文件。
使用重定向方式文件输入输出：

freopen("input.txt", "r", stdin);//从文件input.txt读入 freopen("output.txt", "w", stdout); 12

使用fopen

#include<stdio.h> #define INF 1000000000 int main() {FILE *fin, *fout;fin = fopen("data.in", "rb");fout = fopen("data.out", "wb");int x, n = 0, min = INF, max = -INF, s = 0;while(fscanf(fin, "%d", &x) == 1){s += x;if(x < min) min = x;if(x > max) max = x;n++;}fprintf(fout, "%d %d %.3fn", min, max, (double)s/n);fclose(fin);fclose(fout);return 0; }

12345678910111213141516171819

比较：
重定向的方法写起来简单、自然，但是不能同时读写文件和标准输入输出；fopen的写法稍显繁琐，但是灵活性比较大（例如，可以反复打开
并读写文件）。如果想把fopen版的程序改成读写标准输入输出，只需赋值“fin＝stdin；fout＝stdout；”即可，不要调用fopen和fclose

习题2-1　水仙花数
输出100～999中的所有水仙花数。若3位数ABC满足ABC＝A3＋B3＋C3，则称其为水仙花数。例如153＝13＋53＋33，所以153是水仙花数。

#include <stdio.h> int main() { for(int i = 100;i<=999;i++){ int a=i/100,b=i/10%10,c=i%10; if(i==a*a*a+b*b*b+c*c*c) printf("%dn",i); } return 0; } 1234567891011

习题2-2　韩信点兵
相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入包含多组数据，每组数据包含3个非负整数a，b，c，表示每种队形排尾的人数（a＜3，b＜5，c＜7），输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100。输入到文件结束为止。

#include<stdio.h> int main() { FILE *fin, *fout; // fin = fopen("data.in", "rb"); // fout = fopen("data.out", "wb"); int a,b,c,k=0; while(/*f*/scanf(/*fin, */"%d%d%d", &a,&b,&c)){ k++; int tag = 0, n; for(n = 10;n<=100;n++){ if((n%3==a)&&(n%5==b)&&(n%7==c)){ tag = 1; break; } } if(tag==1) /*f*/printf(/*fout, */"Case %d: %dn",k, n); else /*f*/printf(/*fout, */"Case %d: No answern",k); } // fclose(fin); //fclose(fout); return 0; }

1234567891011121314151617181920212223242526

习题2-3　倒三角形
输入正整数n≤20，输出一个n层的倒三角形。例如，n＝5时输出如下：
#########
  #######
    #####
      ###
        #

#include<stdio.h> int main(){ int n; scanf("%d",&n); for(int i = 0; i < n; i++){ for(int j = 0;j<i;j++) printf(" "); for(int j = 0;j<2*n-2*i-1;j++) printf("#"); printf("n"); } return 0; }

12345678910111213141516

习题2-4　子序列的和
输入两个正整数n＜m＜106，输出 1 n 2 + 1 ( n + 1 ) 2 + ⋅ ⋅ ⋅ + 1 m 2 frac{1}{n^2}+frac{1}{(n+1)^2}+···+frac{1}{m^2} n21+(n+1)21+⋅⋅⋅+m21，保留5位小数。输入包含多组数据，结束标记为n＝m＝0。提示：本题有陷阱。

#include<stdio.h> int main(){ int n,m; double sum,term; while(1){ sum=0; scanf("%d%d",&n,&m); if((n==0)&&(m==0)){ printf("0.00001n"); break; } for(int i = n;i<=m;i++){ term = 1.0/(i*i); sum += term; } printf("%.5fn",sum); } return 0; }

1234567891011121314151617181920212223

习题2-5　分数化小数
输入正整数a，b，c，输出a/b的小数形式，精确到小数点后c位。a,b≤106，c≤100。输入包含多组数据，结束标记为a＝b＝c＝0。

#include <stdio.h> #include <math.h> int main(){ int a, b, c, k=0; while(1){ scanf("%d%d%d", &a, &b, &c); if((a==0)&&(b==0)&&(c==0)) break; k++; printf("Case %d: %d.",k,a / b); for(int i = 1; i <= c; i++){ a = a % b; a *= 10; if (i==c) printf("%dn",int(floor(a*1.0/b+0.5))); else printf("%d",a/b); } } return 0; }

1234567891011121314151617181920212223

习题2-6　排列
用1，2，3，…，9组成3个三位数abc，def和ghi，每个数字恰好使用一次，要求abc：def：ghi＝1：2：3。按照“abc def ghi”的格式输出所有解，每行一个解。提示：不必太动脑筋。

#include<stdio.h> int main(){ int n,m; int a, b, c, d, e, f, g, h, i; for(int j = 123;j<= 329;j++){ a = j/100; b = j/10%10; c = j%10; d = 2*j/100; e = 2*j/10%10; f = 2*j%10; g = 3*j/100; h = 3*j/10%10; i = 3*j%10; if ((a*b*c*d*e*f*g*h*i==1*2*3*4*5*6*7*8*9)&&(a+b+c+d+e+f+g+h+i==45)){//验证每个数字只用了一遍 printf("%d%d%d %d%d%d %d%d%dn",a,b,c,d,e,f,g,h,i); } } return 0; }

123456789101112131415161718192021

题目2。下面的程序运行结果是什么？“！＝”运算符表示“不相等”。提示：请上机实验，不要凭主观感觉回答。

#include<stdio.h> int main() { double i; for(i = 0; i != 10; i += 0.1) printf("%.1fn", i); return 0; } 12345678

结果是死循环，一直运行；
想要输出到10.0的话改为以下程序：

#include<stdio.h> int main(){ double i; for(i = 0;(i-10)<0.01; i += 0.1){ printf("%.1fn", i); } return 0; } 123456789