| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3432 人关注过本帖, 1 人收藏
标题:【求助】c语言,新手,我又 RE 又 MLE 又 TLE 了,不知道怎么办了,帮忙看看 ...
取消只看楼主 加入收藏
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
结帖率:100%
收藏(1)
已结贴  问题点数:10 回复次数:15 
【求助】c语言,新手,我又 RE 又 MLE 又 TLE 了,不知道怎么办了,帮忙看看代码吧>_<
内存和时间要求:(其实还有一个64位什么的我不知道那是什么意思)
         Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
然后是题目,虽然是英文,但是单词都很简单,意思也很好理解,不看英文大概也可以了
Description
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).
 
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
 
Output
For each test case, print the value of f(n) on a single line.
 
Sample Input
 1 1 3
1 2 10
0 0 0
 
Sample Output
 2
5

这是我的第一个代码,用递归,但是RE了
#include<stdio.h>

int main()
{
int n,a,b;
int f(int a,int b,int n);
while(~scanf("%d%d%d",&a,&b,&n))
{
    if(n!=0)
    {
        printf("%d\n",f(a,b,n));
    }
}
return 0;
}
int f(int a,int b,int n)
{

    if(n==1||n==2)
        return 1;
    else
        return (a*f(a,b,n-1)+b*f(a,b,n-2))%7;

}

这是我的第二个代码,申请了一个动态变量f来储存结果,最后的结果是MLE了
#include<stdio.h>
#include<malloc.h>
int main()
{
int n,a,b,i;
int *f=(int*)malloc(sizeof(int)*100000000);
while(~scanf("%d%d%d",&a,&b,&n))
{

    if(n!=0)
    {
        if(n==1||n==2)
            printf("1\n");
        else
        {
             f[0]=1;
             f[1]=1;
             for(i=2;i<n;i++)
                f[i]=(a* f[i-1]+b*f[i-2])%7;
             printf("%d\n",f[n-1]);
        }
     }

   free(f);
}
return 0;
}
最后我垂死挣扎了一下,试着用两个循环来代替递归,又TLE了。。。
#include<stdio.h>
int main()
{
int n,a,b,i,sum1,sum2,sum;
while(~scanf("%d%d%d",&a,&b,&n))
{

    if(n!=0)
    {
        if(n==1||n==2)
            printf("1\n");
        else
        {
            sum1=1;
            sum2=2;
            sum=0;
            for(i=0;i<n-2;i++)
            {
                sum=(sum1*a+sum2*b)%7;
                sum1=sum2;
                sum2=sum;
            }
            printf("%d\n",sum);
        }
     }

}
return 0;
}


我实在没辙了,我是新手,很多东西不懂,求指教,只给大神你自己写的代码也好,顺便传授一下经验也好,帮帮忙~~~~~
搜索更多相关主题的帖子: multiple sequence Memory number c语言 
2014-07-17 01:25
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
我刚刚看了那个“提问的智慧”那个帖子,我才发现原来我问得很没有水准,那么接下来我就把我脑子里面的一系列的疑问都问出来好了,望大神止步!
2014-07-17 01:33
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
对于第一个代码,我想我是没什么好说的了,这个题目用递归来做应该是理所当然的,但是因为n的值可达100,000,000,那么递归的话程序确实是会崩溃,虽然我是新手但这个我还是知道的,所以RE了。所以我尝试着要别的方法
2014-07-17 01:36
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
对于第二个代码,我试图利用增大内存的使用而减少时间的耗费(可以这样说吧。。。。),我想把所有f的值都用一个数组储存起来,直接获取,不用递归,就可以减少运行时间了。但是我知道一个数组最多只能申请都六位数,但n可达100 000 000,所以我用了malloc函数动态申请内存,新学的,希望没有用错,应该没有用错,因为程序是可行的,答案也是对的。但是超内存了。。。。
2014-07-17 01:41
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
对于第三个代码,我是想着用循环应该会比用递归耗费的时间少,所以就用了,发现还是超出限制的时间了
2014-07-17 01:42
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
所以总结来说
1. 递归不行
2.申请大内存储存f的值再调用  也不行
3.用两个循环   也不行

所以我这个帖子主要是问这个题还有什么方法没有,或者应该这样问,这个题的解题思路大概是什么?提个大概我也能懂的,谢谢了~~~~~~


希望明天能有回复
2014-07-17 01:46
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
对了,我忘了考虑遇到三个0就结束这个条件了,不过因为TLE  MLE  RE  什么的就轮不上WA了。。。。不过除了这个其他答案还是对的,也就是说我这三个代码可以得出正确的答案
2014-07-17 01:50
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
第二个代码的sum2和sum1调换过来才对,代码交了很多次都乱掉了,我刚刚又试了一次,发现调换过来才是对的。 另外我的多组数据输入的方式应该有误,因为要以0 0 0结束。哎呀,又发现一个问题了。。。。 不过我最想知道的是算法或者解题思路什么。   我都睡不着了。。。
2014-07-17 02:03
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
回复 9 楼 vvvcuu
嗯嗯,非常感谢你的回答!今天早上学长也讲了解法,跟学长讲的方法差不多,就是找出呈现循环的那些f。谢谢你了!

[ 本帖最后由 xuanyuxian 于 2014-7-17 19:26 编辑 ]
2014-07-17 17:08
xuanyuxian
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2014-7-17
收藏
得分:0 
以下是引用vvvcuu在2014-7-17 10:11:11的发言:

当A和B给定以后,f(n)将会按一定的规律出现,呈现一定的循环.因此,只需要考虑A,B即可.
设定一个数组,比如a[1000], 依次计算从1到n的f(n),令i表示循环参照量.把每次计算的f(i),依次存入数组a[]中, 设置另一个变量k,k=i/2. 依次比较a[0]到a[k-1]和a[k]到a的值(k=2;k<=i;k+=2),这个地方比较浪费时间,如果相等,跳出循环,可能需要goto,记录下此时的i值,然后计算n%i, 最后f(n)=a[n%i+k].
 
简单的描述了下算法, 还没写具体的代码, 一会儿写一下看看能行不.
 
初步估计,只要比较连续的7个数字相等就可以停止计算了.  亲测对于不同的a,b,当n=50的时候,最大的循环尽管到达30多,但并没有出现连续的7个数字和后面数字相等的情况.
 
个人认为,存入数组然后取出来直接用要比递归快得多. 递归只适合运算规模不大的情况下. 就这个题来说,递归1个亿的运算规模一般的计算机都需要很长时间的.
我自己测试的类似你的第一个的代码的程序, 循环依次输出50个数字的情况下就接近一分钟了.
2014-07-17 17:09
快速回复:【求助】c语言,新手,我又 RE 又 MLE 又 TLE 了,不知道怎么办了,帮 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.057023 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved