洗澡（C语言代码）

原题链接：题目506 - ACM在线评测系统

描述：

Mostrp是个爱干净的好少年。 有一次去澡堂洗澡时发现 澡堂的澡柜编号中没有出现过数字‘4’。 Mostrp 感到很好奇。可能是因为在澡堂老板眼里。数字‘4’是十分不吉利的。现在Mostrp知道澡柜的最大的编号N，你能帮他算出澡堂一共有多少澡柜吗？

输入：

有多组数据，每行输入一个N。
( 1 <= N <= 50000 )

输出：

输出澡柜的个数，输出占一行。

样例输入：

3

41

399

50000

样例输出：

3

36

323

26244

解题思路：

最多N个澡柜有编号，遍历N以内的正整数，如果某编号在某位有4，就减去这个编号。

注意事项：

有的算法虽然快，能覆盖大部分用例，但是仍有缺陷，有待优化。

参考代码：

#include<stdio.h>
int main(){
	int i,n,c,N;
	while(~scanf("%d",&N)){
		c=N;//最多有N个澡柜
		for(i=1;i<N;i++){//遍历N以内的正整数
			n=i;
			while(n){
				if(4==n%10){//某数在某位有4
					c--;//没有这个澡柜
					break;
				}
				n/=10;//寻找该数的更高位
			}
		}
		printf("%d\n",c);
	}
	return 0;
}

下面还有递归的方法，以及DFS(Depth-First-Search)深度优先搜索算法，当N=41时结果是35，与答案36不相符。

/*
查看代码---运行号：2490709----结果：Accepted
运行时间：2018-05-22 11:22:57  |  运行人:ACM_李朝强
*/
#include<stdio.h>
int a[10];
int dp[10];
int dfs(int pos,int last){
	int len,ans;
	if(!pos) return 1;
	if(!last&&dp[pos])
		return dp[pos];
	len=last?a[pos]:9;
	ans=0;
	for(int i=len;i>=0;i--)
		ans+=i==4?0:dfs(pos-1,last&&i==len);
	if(!last)
		dp[pos]=ans;
	return ans;
}
int solve(int n){
	int len=0;
	while(n)
		a[++len]=n%10,n/=10;
	return dfs(len,1)-1;
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF)
		printf("%d\n",solve(n));
    return 0;
}

还有更快的，几乎找到了公式，加了注释后如下：

/*
查看代码---运行号：371556----结果：Accepted
运行时间：2013-03-31 16:08:44  |  运行人:王力伟
*/
#include<stdio.h>
int main(){
	int n,s;
	while(~scanf("%d",&n)){//n作为澡柜编号，每位不可能包含4
		s=0;//s表示不存在的澡柜个数
		if(n>4) s=(n+6)/10;//当n属于[5,39]，s属于[1,4]
		//当n为41，不存在的编号为4,14,24,34,40，只有5个，答案是13个，答案错误
		/*当n为399，不存在的编号为
		4,14,24,34,40,41,42,43,44,45,46,47,48,49,54,64,74,84,94,
		104,114,124,134,140,141,142,143,144,145,146,147,148,149,154,164,174,184,194,
		204,214,224,234,240,241,242,243,244,245,246,247,248,249,254,264,274,284,294,
		304,314,324,334,340,341,342,343,344,345,346,347,348,349,354,364,374,384,394
		，有76个，答案正确*/	
		if(n>40) s+=(n+60)/100*9;
		if(n>400) s+=(n+600)/1000*81;
		if(n>4000) s+=(n+6000)/10000*729;
		if(n>40000) s+=(n+60000)/100000*729*9;
		printf("%d\n",n-s);
	}
	return 0;
}

这之后，找到了可接受的方法，用空间换效率，a[max]保存从1到max-10的编号，用例再多也不怕时间超限：

/*
查看代码---运行号：2456688----结果：Accepted
运行时间：2018-04-16 21:57:51  |  运行人:ycxy06104
*/
#include<stdio.h>  
#define max 50010  
int a[max];  
  
int cmp(int n)  
{  
    while(n)  
    {  
        if(n%10==4)  
           return 1;  
        n=n/10;  
    }  
    return 0;     
}  
  
int main()  
{  
    int n;  
    for(int i=1;i<=50000;i++)  
    {  
        if(cmp(i))  
           a[i]=a[i-1];  
        else   
           a[i]=a[i-1]+1;  
    }  
    while(scanf("%d",&n)!=EOF)  
       printf("%d\n",a[n]);  
    return 0;  
}