题解"/>
失踪的7题解
这里附上题目链接:失踪的7。
题目描述
远古的Pascal人也使用阿拉伯数字来进行计数,但是他们又不喜欢使用7,因为他们认为7是一个不吉祥的数字,所以Pascal数字8其实表示的是自然数中的7,18表示的是自然数中的16。下面计算一下,在正整数n范围以内包含有多少个Pascal数字。
思路解析
注意:n是以Pascal数字形式输入的,即n不能含有数字7!!!
根据题意,显然此题就是让我们计算在1到n的所有整数中有多少个不含7的数。
探索规律
- n每增加10(n≠70),含7数字个数加1个,Pascal数字增加9^1个;
- n每增加100(n≠700),含7数字个数加10+9×1个,Pascal数字增加9^2个;——②
- n每增加1000(n≠7000),含7数字个数加100+9×(10+9×1)个,Pascal数字增加9^3个;——③
- n每增加10000(n≠70000),含7数字个数加1000+9×(100+9×(10+9×1))个,Pascal数字增加9^4个;——④
…………
规律归纳
设A(i)代表n的第i位数(i=1、2、……、m),
解释
因为Pascal数字中没有7,所以Pascal数字的每一位只能用9个不同数字来表示。我们将Pascal数字总数先设为0,对于给出的n进行逐位分析。
- 当个位<7时,Pascal数字总数增加数为个位数个9^0;个位>=7时,Pascal数字总数增加数为个位数-1。6的Pascal数字个数为6,8的Pascal数字个数为7。
- 当十位<7时,由规律探索的第一条,相当于n从0增加了十位数个10,Pascal数字增加了十位数个9^1;十位>=7时,Pascal数字总数增加数为个位数-1个 9^1。
- 依此类推……
AC代码
#include <stdio.h>
#include <stdlib.h>int main()
{long long j=0;//j必须使用long long类型,否则数据会溢出long long sum=0;int t,i,k=1;long long pascal[100000]={0};scanf("%d",&t);for(i=0;i<t;i++)//共有t组测试数据{scanf("%lld",&pascal[i]);}for(i=0;i<t;i++){j=pascal[i];while(j!=0){if((j%10)>=7){sum+=(j%10-1)*k;}else{sum+=(j%10)*k;}j/=10;k=k*9;}printf("%lld\n",sum);k=1;sum=0;}return 0;
}
不当之处,敬请斧正……
更多推荐
失踪的7题解
发布评论