求解c语言中数从一到n中一出现次数的问题，一下是老师的代码，老师说还可以用递归的方法。求解释。// 1的传奇 :数1的个数
#include <stdio.h>
int main(){
int cnt=0,c,i,k,n,X=1;
scanf("%d",&n);
for (i=1; k=n/i; i*=10) {
cnt += (k / 10) * i; // k/10为高位的数字
c=k%10; // 当前位的数字
if (c>X) cnt += i;
else if (c==X) cnt += n - k * i + 1;
// n-k*i为低位的数字
}
printf("%d", cnt);
return 0;
}
收藏于10-22
问题可以说成是：对数数据N，在从1到N的所有数值中，各个数位上出现的1的次数的统计。
这个问题的解决是按如下思路来的：1. 首先，统计的方式是从个位开始，依次统计个,十,百,千, ... ... 各个数位上的1的个数。2. 当统计完所有数据个位上的1的个数以后，我们还需要统计这些数据十位及以上的各位的一的个数，也就是不考虑个位了。既然不考虑个位，那就相当于把原来的数据个位都去掉，也就是把原来的数除以10，来统计了；此时，原来的十位成为了个位，这个问题就又转换成了统计个位上1的个数的问题了。要注意的是，此时各位的一个1，实际上是10个，因为这一个位为1时，个位是可以从0到9变化的；同理，当百位上有一个1时，实际上有100个数的百位1（十位个位从00到99，共100个数），3. 重复第二步，直到没有更高的有效数位。
那么如何来统计这些数个位上1的个数呢：
对于一个两位数N，如果它的十位数为n，则这些数中个位上的1的个数为 n或者n+1，是否+1，要看个位上的数字是否大于等于1，是则加，不是则不加。如N为55，则个位是1的数据共有5+1个（这些数分别是1,11,21,31,41, 再加上51），这个+1就是因为个位的5大于1（包括了最后的那个51）；而N为50时，则个位是1的数据共有5个，没有+1，就是因为个位的0小于1（不能包括最后的51）。
以上的结论实际上是可以推广至位数大于2的情况。比如N=231，则从1到231的所有231个数中，个位上1的个数为23+1=24个（1-99之间10个,100-199之间10个，200-231之间4个）。
这样一来，上面的代码就不难理解了
#include <stdio.h>int main(){
int cnt=0,c,i,k,n,X=1;
scanf("%d",&n);
for (i=1; k=n/i; i*=10) {
// i的变化为1， 10， 100， 1000， .....
// 则k就是原数据、原数据/10、原数据/100、原数据/1000、....
cnt += (k / 10) * i; // k/10为个位以上的各位数字
c=k%10; // 当前位的数字
if (c>X) cnt += i; 当前位的1，代表有i个数这个位都是1
else if (c==X) cnt += n - k * i + 1;
// n-k*i为低位的数字
}
printf("%d", cnt);
return 0;
}
