算法优化问题

独一无②

问题一：
输入钱币，输出兑换成 3分，2分， 1分 面值的人民币方法有几种。我发现用循环做，速度会很慢很慢。
样例输入：12553   输出：13137761

1. # include <stdio.h>
   
2. int main()
   
3. {
   
4.      int a,j,k,i,sum,num=0;
   
5.      scanf("%d",&a);
   
6.      for(j=1;j<=a;j++)
   
7.      {
   
8.         for(k=1;k<=a/2;k++)
   
9.         {
   
10.           for(i=1;i<=a/3;i++)
    
11.           {
    
12.               sum=i*3+k*2+j;
    
13.               if(sum == a)
    
14.                 num++;
    
15.           }
    
16.         }
    
17.      }
    
18.         printf("%d\n",num);
    
19.         return 0;
    
20. }

复制代码

问题二：
输入 n,求n的n次方的结果最右边那位数。
如 输入5
5*5*5*5*5=3125
输出结果 应为 5；

1. # include <stdio.h>
   
2. # include <math.h>
   
3. int main()
   
4. {
   
5.    int a,b;
   
6.    long c,d;
   
7.    scanf("%d",&a);
   
8.    for(b=1;b<=a;b++)
   
9.    {
   
10.       scanf("%ld",&c);
    
11.       d=pow(c,c);
    
12.       d=d%10;
    
13.       printf("%ld\n",d);
    
14.    }
    
15. }

复制代码

上面的那二个问题，但输入数很大时，我写的代码都不可行，运行太慢了，求优化算法的方法。

春在溪头荠菜花

第一题：
# include <stdio.h>
int main(){
       
        int i,j,k,n,ans=0;
        scanf("%d",&n);
        int boun1=n/3,boun2=n/2;
        for(i=0;i<=boun1;++i){
                for(int j=0;j<=boun2;++j){
                        if(i*3+j*2<=n)
                        ++ans;
                }
        }
        printf("%d\n",ans);
        return 0;
}

第二题：
# include <stdio.h>
typedef long long int ll;
int main(){
        ll n;
        int last,i;
        scanf("%lld",&n);
        last=n%10;
        if(last<2||last==5||last==6||last==9){
                ;
        }else if(last==2||last==8){
                if(!(n%4))
                last=6;
                else
                last=4;
        }else if(last==4){
                last=6;
        }else if(last==3){
                i=n%4;
                switch(i){
                case 0: last=1;break;
                case 1: last=3;break;
                case 2: last=9;break;
                case 3: last=7;break;               
                default:break;               
                }
               
        }else if(last==7){
                i=n%4;
                switch(i){
                case 0: last=1;break;
                case 1: last=7;break;
                case 2: last=9;break;
                case 3: last=3;break;               
                default:break;               
                }
        }
        printf("%d\n",last);
       
}
应该还有更好的算法，这块应该算数论的内容吧:smile

独一无②

怎么没有人啊！:cry求帮助！！！

y290176346

第一个问题没看明白问题 和想要的结果，请详细一点，第二个问题输入 n,求n的n次方的结果最右边那位数，这个n 是一个数吗？

独一无②

y290176346 发表于 2015-11-21 16:50
第一个问题没看明白问题 和想要的结果，请详细一点，第二个问题输入 n,求n的n次方的结果最右边那位数，这个 ...

将输入的数转换为1分，2分，3分钱币 的方法有几种。下面那题 n就是输入的数，如例题的5.

y290176346

我理解的你第二个问题 是 比如说32 就是32乘以自己的32次方，如果是这样的话我给你个提示，比如说各位是1的 和各位是1的两个数无论乘以多上次 结果个位都是1,个位是6的和各位是6的两个数无论乘以多少次都是6  个位是9 的和各位是9的两个数无论乘以多少次 各位要么是 1 要么是9，你可以根据这个思路找找规律来接话算法

独一无②

y290176346 发表于 2015-11-21 16:58
我理解的你第二个问题 是 比如说32 就是32乘以自己的32次方，如果是这样的话我给你个提示，比如说各位是1的 ...

好的，谢谢。第一个问题，比如把5分钱，转换成 3分，2分， 1分的转换方法有几种。只有（3+1+1），（1+ 1+1+1+1），（3+2），（2+2+1），（1+1+1+2），5种。

Alan_Ciao

第二个问题：

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         long n, i;
   
6.         int x = 1;
   
7. 
   
8.         printf("请输入一个正整数: ");
   
9.         scanf("%ld", &n);
   
10. 
    
11.         for (i = 0; i < n; i++)
    
12.         {
    
13.                 x = (x * n) % 10;
    
14.         }
    
15. 
    
16.         printf("结果为: %d\n", x);
    
17. 
    
18.         return 0;
    
19. }

复制代码

思路是把n连续乘n次，就是n的n次方，每一次相乘都只取出各位数然后再继续相乘，最后只保留个位上的数字就可以了。
我也是初学，不知到这样的算法可不可以。还有数太大了不知道怎么验证结果的正确性。

独一无②

Alan_Ciao 发表于 2015-11-21 19:06
第二个问题：

算法是对的，但是数据大的时候，输出时间结果还是太慢了。还有更好的优化算法吗？

Alan_Ciao

独一无② 发表于 2015-11-21 19:28
算法是对的，但是数据大的时候，输出时间结果还是太慢了。还有更好的优化算法吗？

这个。。。具体要多大的数呢？是不是都已经超过4个字节的范围了？

y290176346

Alan_Ciao

独一无② 发表于 2015-11-21 19:28
算法是对的，但是数据大的时候，输出时间结果还是太慢了。还有更好的优化算法吗？

那就只想到找规律了，感觉有点作弊。。。

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         unsigned long n;
   
6.         int m;
   
7. 
   
8.         printf("请输入一个正整数: ");
   
9.         scanf("%ld", &n);
   
10. 
    
11.         m = n % 10;
    
12.        
    
13.         switch (m)
    
14.         {
    
15.         case 0:
    
16.         case 1:
    
17.         case 5:
    
18.         case 6:
    
19.                 printf("结果为: %d\n", m);
    
20.                 break;
    
21.         case 8:
    
22.         case 2:
    
23.                 if (n % 4 == 2)
    
24.                         printf("结果为: 4\n");
    
25.                 else
    
26.                         printf("结果为: 6\n");
    
27.                 break;
    
28.         case 3:
    
29.                 if (n % 4 == 1)
    
30.                         printf("结果为: 3\n");
    
31.                 else
    
32.                         printf("结果为: 7\n");
    
33.                 break;
    
34.         case 7:
    
35.                 if (n % 4 == 1)
    
36.                         printf("结果为: 7\n");
    
37.                 else
    
38.                         printf("结果为: 3\n");
    
39.                 break;
    
40.         case 4:
    
41.                 printf("结果为: 6\n");
    
42.                 break;
    
43.         case 9:
    
44.                 printf("结果为: 9\n");
    
45.                 break;
    
46.         }
    
47. 
    
48. 
    
49.         return 0;
    
50. }

复制代码

独一无②

Alan_Ciao 发表于 2015-11-21 20:24
那就只想到找规律了，感觉有点作弊。。。

虽然有点作弊，但是也是一种解决方法。我连规律都找不出，谢谢~

bloodbat007

用寄存器变量

dps521

过来看看一起学习一下
:smile:smile:smile

独一无②

春在溪头荠菜花 发表于 2015-11-21 14:39
第一题：
# include
int main(){

算法一为什么 是boun1 是外循环，不是boun2 大一点，所以boun2 是外循环吗？