大一c语言习题，求大佬解答。

题目如图，此题难点在于控制时间，很容易时间超限，我提交之后时间超限的图也在下面。

public boolean is6(num){
if(num%10==0){
return false}else if (num%10==6){
return true;
}else{
return is6(num/10);
}
}

public static main(string[] args){
int count=0;
for(i=1;i < input;i++){
if(is6(i)){
count++;
}
}
printif(count);
}

代码你翻译一下就可以了

肯定不能逐个数循环判断，找出6的个数和输入正整数n的位数的关系式，即可得解。

int count = 0;
foreach(int i in 100)
{
if(i.Tostring().Contains("6"))
{
count++;
}
}
printif(count);

排列组合知识
0到9 有9个不含6的
0到99 有9*9 81个不含0的.....
如果那个数是897
可以将他拆分为0到99，100到199...7到799，800到809，810到819...890到897
将特别注意600到699和860到869和890到897

你也可以找规律
0到9 1个
0到99 9+10-1 因为60到69这个区间
可以列出一个递归函数，将这个函数返回的值存到数组
接着一样的拆分方式
递归一下就行了

public boolean is6(num){
if(num%10==0){
return false}else if (num%10==6){
return true;
}else{
return is6(num/10);
}
}

public static main(string[] args){
int count=0;
for(i=1;i < input;i++){
if(is6(i)){
count++;
}
}
printif(count);
}

/*
**代码如下
*/
4
5 bool Determine_Whether_Contains_6(int num)
6 {
7 do{
8 if(num%10 == 6)
9 {
10 return true;
11 }//end if(num%10 == 6)
12 }while( num /= 10);
13 return false;
14 }//end bool Determine_Whether_Contains_6(int num)
15 int main(void)
16 {
17 int num = 0;
18 int i = 0;
19 int cnt =0;
20 printf("input u need num!!\n");
21 scanf("%d",&num);
22
23 for(i=1; i<=num; i++)
24 {
25 cnt += Determine_Whether_Contains_6(i);
26 }//end for(i=1; i<=num; i++)
27 printf("cnt = %d\n",cnt);
28 }//end int main(void)
29

1 #include
2 #include
3 #include
4 using namespace std;
5 int dp[20][3];
6 int digit[20];
7
8 int dfs(int pos,int sta,bool limit)
9 {
10 if(pos==0) return sta==1;
11 if(!limit&&dp[pos][sta]!=-1)
12 return dp[pos][sta];
13 int ans=0;
14 int up=limit?digit[pos]:9;
15 for(int i=0;i<=up;i++){
16 int nsta=0;
17 if(sta||i==6) nsta=1;
18 ans+=dfs(pos-1,nsta,limit&&i==up);
19 }
20 if(!limit) return dp[pos][sta]=ans;
21 return ans;
22 }
23
24 int solve(int x)
25 {
26 int len=0;
27 while(x){
28 digit[++len]=x%10;
29 x/=10;
30 }
31 return dfs(len,0,true);
32 }
33
34 int main()
35 {
36 int n;
37 memset(dp,-1,sizeof(dp));
38 while(scanf("%d",&n)==1)
39 {
40 printf("%d\n",solve(n));
41 }
42 return 0;
43 }