一道OJ的题 程序超时怎么解决,求大神指导.

一道OJ的题 程序超时怎么解决,求大神指导.
Problem 1036 - Cards
Time Limit: 1000MS Memory Limit: 65536KB Difficulty: 3
Total Submit: 1315 Accepted: 374 Special Judge: No
Description
Magicpig and Kinfkong come to like playing cards recently. Magicpig knows that Kinfkong is very good at mathematics, so he often asks Kinfkong
some very hard problems in order to baffle him. You know, Kinfkong is very clever, so he can defeat Magicpig each time.
One day, Magicpig takes out a pile of n cards and asks Kinfkong a question: "Now I have n cards in my hand. We do't care about the face value
of the cards, so we consider them to be the same. Now you can take some cards from my hand. Each time you can take 1,2 or 3 cards.
Repeat this step until there is no more card in my hand. Now I want to know how many different ways can you take away all the cards
from my hand. I give you 10 minutes. If you can't figure out the answer, you are defeated."
You are a friend of Kinfkong. Now Kinfkong can not figure out the answer and there is no time left! He knows you are an excellent ACMer, so he
needs you help!
Input
The input contains one or more data sets. Each data set consists of a positive integer n(
诸葛阿黑传 1年前 已收到1个回答 举报
赞

huashanrenjian 幼苗

共回答了16个问题采纳率：87.5% 举报

我就想问一下你提交的时候把system("pause");删除了没有?
如果没删除,的确会出现RE的情况
其他的我还没来得及看

1年前 追问

1

诸葛阿黑传 举报

删除了，还是不行

举报 huashanrenjian

建议你不要开个数组存n

也就是可以把输入n和输出都写到while循环里

因为输入一个就立即输出对应的结果在编译器看来跟输入结束再输出所有结果是一样的

而且前者占用内存更小

再有就是检查你的sort函数是否有问题，递归算法是否周全（我检查了一遍，应该没问题）

实在不行我帮你写一份

祝学业顺利

我帮你改了改

你再试试

#include 
#include 
int count=0;
void sort(int n){
 if(n==0){count++;return;}
 if(n-1<0) return;
 else sort(n-1);
 if(n-2<0) return;
 else sort(n-2);
 if(n-3<0) return;
 else sort(n-3);
}

int main(){
int n[10000];
int i=0,j;
scanf("%d",&n[i]);
while(1) 
{
if(n[i]==0)break;
i++;
scanf("%d",&n[i]);
}
for(j=0;j{
count=0;
sort(n[j]);
printf("%dn",count);
}
return 0;
}

诸葛阿黑传 举报

还是不行，不过还是真心感谢，难道是算法的时间复杂度太高？难不成要重新设计算法？我所能想到的也只是这样的搜索方法了。

举报 huashanrenjian

绝对不是 一定是你少输出了一个结果，导致系统等待你输出结果 最后才超时了 检查一下边界条件吧，很可能是这里的问题 实在不行就再写一遍，反正代码不多 再写一遍说不定就发现错误了 真的抱歉，没能帮你解决问题，sorry~ 对了，你看的懂C++么？ 我要不用C++帮你写一下，你提交一下试试？ 另外：你这几次提交选择的代码类型是C吧？如果选了C++可能也会RE

诸葛阿黑传 举报

C++也学过，看得懂，虽然没C那么熟，如果能得一份那自然最好，那就太感谢了！

举报 huashanrenjian

#include 
using namespace std; 
int count=0;
void sort(int n){
 if(n==0){count++;return;}
 if(n-1<0) return;
 else sort(n-1);
 if(n-2<0) return;
 else sort(n-2);
 if(n-3<0) return;
 else sort(n-3);
}
 
int main(){
int n;
cin>>n; 
while(n!=0) 
{
count=0; 
sort(n);
cout<cin>>n;
}
return 0;
}

大概就是这样，你试试（注意选语言时C++）

可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 5.010 s. - webmaster@yulucn.com