算法优化问题

独一无②

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

# include <stdio.h>
int main()
{
     int a,j,k,i,sum,num=0;
     scanf("%d",&a);
     for(j=1;j<=a;j++)
     {
        for(k=1;k<=a/2;k++)
        {
          for(i=1;i<=a/3;i++)
          {
              sum=i*3+k*2+j;
              if(sum == a)
                num++;
          }
        }
     }
        printf("%d\n",num);
        return 0;
} 

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

# include <stdio.h>
# include <math.h>
int main()
{
   int a,b;
   long c,d;
   scanf("%d",&a);
   for(b=1;b<=a;b++)
   {
      scanf("%ld",&c);
      d=pow(c,c);
      d=d%10;
      printf("%ld\n",d);
   }
}

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

春在溪头荠菜花

第一题：
# 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

第二个问题：

#include <stdio.h>

int main(void)
{
        long n, i;
        int x = 1;

        printf("请输入一个正整数: ");
        scanf("%ld", &n);

        for (i = 0; i < n; i++)
        {
                x = (x * n) % 10;
        }

        printf("结果为: %d\n", x);

        return 0;
}

思路是把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
算法是对的，但是数据大的时候，输出时间结果还是太慢了。还有更好的优化算法吗？

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

#include <stdio.h>

int main(void)
{
        unsigned long n;
        int m;

        printf("请输入一个正整数: ");
        scanf("%ld", &n);

        m = n % 10;
        
        switch (m)
        {
        case 0:
        case 1:
        case 5:
        case 6:
                printf("结果为: %d\n", m);
                break;
        case 8:
        case 2:
                if (n % 4 == 2)
                        printf("结果为: 4\n");
                else
                        printf("结果为: 6\n");
                break;
        case 3:
                if (n % 4 == 1)
                        printf("结果为: 3\n");
                else
                        printf("结果为: 7\n");
                break;
        case 7:
                if (n % 4 == 1)
                        printf("结果为: 7\n");
                else
                        printf("结果为: 3\n");
                break;
        case 4:
                printf("结果为: 6\n");
                break;
        case 9:
                printf("结果为: 9\n");
                break;
        }


        return 0;
}

独一无②

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

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

bloodbat007

用寄存器变量

dps521

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

独一无②

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

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