算法优化问题
本帖最后由 独一无② 于 2015-11-21 16:56 编辑问题一：
输入钱币，输出兑换成 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求帮助！！！ 第一个问题没看明白问题 和想要的结果，请详细一点，第二个问题输入 n,求n的n次方的结果最右边那位数，这个n 是一个数吗？ y290176346 发表于 2015-11-21 16:50
第一个问题没看明白问题 和想要的结果，请详细一点，第二个问题输入 n,求n的n次方的结果最右边那位数，这个 ...
将输入的数转换为1分，2分，3分钱币 的方法有几种。下面那题 n就是输入的数，如例题的5. 我理解的你第二个问题 是 比如说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种。 第二个问题：
#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
第二个问题：
算法是对的，但是数据大的时候，输出时间结果还是太慢了。还有更好的优化算法吗？ 独一无② 发表于 2015-11-21 19:28
算法是对的，但是数据大的时候，输出时间结果还是太慢了。还有更好的优化算法吗？
这个。。。具体要多大的数呢？是不是都已经超过4个字节的范围了？
\
本帖最后由 y290176346 于 2015-11-21 20:05 编辑独一无② 发表于 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
那就只想到找规律了，感觉有点作弊。。。
虽然有点作弊，但是也是一种解决方法。我连规律都找不出，谢谢~ 用寄存器变量 过来看看一起学习一下
:smile:smile:smile 春在溪头荠菜花 发表于 2015-11-21 14:39
第一题：
# include
int main(){
算法一为什么 是boun1 是外循环，不是boun2 大一点，所以boun2 是外循环吗？
页:
[1]