C语言程序设计100例之（3）： Cantor表
例3 cantor表
题目描述
现代数学的著名证明之一是georg cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：
1/1 1/2 1/3 1/4 ……
2/1 2/2 2/3 ……
3/1 3/2 ……
4/1 ……
……
现以z字型方法给上表的每项编号。方法为：第一项是1/1，然后是1/2、2/1、3/1、2/2、1/3、1/4、2/3……。
输入格式
整数n（1≤n≤10000000）
输出格式
表中的第n项
输入样例
7
输出样例
1/4
（1）编程思路1。
可以把上面的数表右转45度，成一金字塔形状，如下所示：
1/1
2/1 1/2
3/1 2/2 1/3
4/1 3/2 2/3 1/4
…… …… …… ……
该金字塔第1行有1个数，第2行有2个数，…，第i行有i个数。并且第i行上的i个分数的分子从i~1，分母从1~i，即第1个分数为i/1，最后一个分数为1/i。
为输出数表中的第n项，先需计算这一项在第几行。设第n项在x行，由于前x-1行共有1+2+3+…+（x-1）项，前x行有1+2+…+x项，因此有：
可以用一个循环计算第n项所在的行数，如下：
for (i=1； i*(i+1)/2<n； i++) ；
循环退出后，i*(i+1)/2刚好大于或等于n，因此，i就是第n项所在的行。
第n项在第i行中属于第几项又可以计算出来，公式为：
即n减去前i-1行中的全部项数。
由于是以z字型方法给数表的每项编号，因此当行号为奇数时，编号从左往右进行；当行号为偶数时，编号从右往左进行。
这样，当i为奇数时，第i行的第k项为（i+1-k）/（k）；当i为偶数时，第i行的第k项为（k）/（i+1-k）。
（2）源程序1。
#include <stdio.h>
int main()
{
int i,k,n;
scanf("%d",&n);
for (i=1; i*(i+1)/2<n; i++) ;
k=n-(i*(i-1)/2);
if (i%2!=0)
printf("%d/%d\n",i+1-k,k);
else
printf("%d/%d\n",k,i+1-k);
return 0;
}
（3）编程思路2。
通过循环的方式直接模拟求出第n个数应该位于第row行第s列。
（4）源程序2。
#include <stdio.h>
int main()
{
int n,s,row;
scanf("%d",&n);
row=1;
s=1;
while (s<n)
{
row++;
s+=row;
}
s=n-(s-row);
if (row%2==1)
printf("%d/%d\n",(row-s)+1,s);
else
printf("%d/%d\n",s,(row-s)+1);
return 0;
}
习题3
3-1 金币
本题选自洛谷题库 （https://www.luogu.org/problem/p2669）
题目描述
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续n天每天收到n枚金币后，骑士会在之后的连续n+1天里，每天收到n+1枚金币。
请计算在前k天里，骑士一共获得了多少金币。
输入格式
一个正整数k，表示发放金币的天数。
输出格式
一个正整数，即骑士收到的金币数。
输入样例#1
6
输出样例#1
14
输入样例#2
1000
输出样例#2
29820
说明/提示
【输入输出样例 1 说明】
骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。
（1）编程思路1。
为计算在前n天里，骑士一共获得了多少金币。需要确定第n天发几枚金币。设第n天发x枚金币，由于发x-1枚金币可发1+2+3+…+（x-1）天，发x枚金币可发1+2+…+x天，因此有：
可以用一个循环计算第n天发的金币数，如下：
for (i=1； i*(i+1)/2<n； i++) ；
循环退出后，i*(i+1)/2刚好大于或等于n，因此，i就是第n天发的金币数。1~i-1枚金币一定发满了相应的天数，即每天1枚金币发了1天，每天2枚金币发了2天，…，每天i-1枚金币发了i-1天，先用循环累积每天发1~i-1枚金币共发了多少，再加上每天发i枚金币发的数目即可得到答案。
（2）源程序1。
#include <stdio.h>
int main()
{
int n,m,k,s,i;
scanf("%d",&k);
for (n=1; n*(n+1)/2<k; n++);
n--;
m=(1+n)*n/2;
for (s=0,i=1;i<=n;i++)
s+=i*i;
if (k-m>0)
s+=(k-m)*(n+1);
printf("%d\n",s);
return 0;
}
（3）编程思路2。
直接模拟发金币过程。用一个二重循环完成，外循环控制发的天数，循环体中用内循环控制k枚金币连发k天。
（4）源程序2。
#include <stdio.h>
int main()
{
int n,k=1,i=1,j,sum=0;
scanf("%d",&n);
while(i<=n) // 一直循环下去，直到
{
for(j=1;j<=k;j++) // 连给k天
{
sum=sum+k; // 加上今天获得的钱
i++; // 总天数增加
if(i>n)
{
break;
}
}
k++; // 连给天数增加
}
printf("%d\n",sum);
return 0;
}
3-2 盐水的故事
problem description
挂盐水的时候，如果滴起来有规律，先是滴一滴，停一下；然后滴二滴，停一下；再滴三滴，停一下...，现在有一个问题：这瓶盐水一共有vul毫升，每一滴是d毫升，每一滴的速度是一秒（假设最后一滴不到d毫升，则花费的时间也算一秒），停一下的时间也是一秒这瓶水什么时候能挂完呢？
input
输入数据包含多个测试实例，每个实例占一行，由vul和d组成，其中 0<d<vul<5000。
output
对于每组测试数据，请输出挂完盐水需要的时间，每个实例的输出占一行。
sample input
10 1
sample output
13
（1）编程思路。
先计算vul毫升盐水需要滴多少滴滴玩。显然，滴数n=(int)(vul/d); ，若最后一滴不到d毫升，花费的时间也算一秒，因此要注意滴数达到精度的要求，可进行如下校正：
if (vul-n*d>0.00001) n++;
为计算挂完盐水需要的时间，需要确定中间停顿的次数。设滴玩n滴盐水需要滴x次，由于前x-1次可滴下1+2+3+…+（x-1）滴盐水，前x次可滴下1+2+…+x滴盐水，因此有：
可以用一个循环计算滴玩n滴盐水需要的次数，如下：
for (i=1； i*(i+1)/2<n； i++) ；
循环退出后，i*(i+1)/2刚好大于或等于n，因此，i就是滴玩n滴盐水需要的次数。每两次之间会停顿，因此停顿时间为i-1秒，加上n滴用时n秒即得所求答案。
（2）源程序。
#include <stdio.h>
int main()
{
double vul,d;
int s,n;
while (scanf("%lf%lf",&vul,&d)!=eof)
{
s=(int)(vul/d);
if (vul-s*d>0.00001) s++;
for (n=1; n*(n+1)/2<s; n++);
n--;
printf("%d\n",s+n);
}
return 0;
}
3-3 peter的烟
题目描述
peter 有n根烟，他每吸完一根烟就把烟蒂保存起来，k(k>1)个烟蒂可以换一个新的烟，那么 peter 最终能吸到多少根烟呢？
输入格式
测试数据包含多组，每组测试数据一行包括两个整数n,k(1<n,k≤108 )。
输出格式
对于每组测试数据，输出一行包括一个整数表示最终烟的根数。
输入样例
4 3
10 3
100 5
输出样例
5
14
124
（1）编程思路。
设变量sum代表peter可抽烟的总根数，n代表烟蒂数，因为peter有n根烟，因此初始时，sum=n（可抽n根烟），烟蒂数为n（n根烟产生n个烟蒂）。
之后不断用烟蒂换烟抽，由于k个烟蒂换一根烟，因此不断执行
sum =sum+ n/k; （n个烟蒂换抽n/k根烟）
n = n/k + n%k; （n/k根烟产生n/k个烟蒂，加上前面换烟后多余的不足换1根烟的n%k个烟蒂为新的烟蒂数）
重复这个过程直到剩下的烟蒂数不足以换根烟。
（2）源程序。
#include <stdio.h>
int main()
{
int n,k,sum;
while(scanf("%d%d",&n,&k)!=eof)
{
sum = n;
while(n >= k)
{
sum += n/k;
n = n/k + n%k;
}
printf("%d\n",sum);
}
return 0;
}