Question

一道C/C++程序题

题目:当M为0时,A[0]=0;当M大于0时,A[M]=A[M-1]-M.若这个A[M]小于等于0或者其值已经出现在A数组中,则用另外一公式A[M]=A[M-1]+1.求输入一个数K,输出A[K]的值.数组值为0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 ...K值最大为50万

原题是英文的:The Recaman's sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−1 + m. (m是下标)
The first few numbers in the Recaman's Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 ...
Given k, your task is to calculate ak.

#include<iostream>
using namespace std;
int a[500001];
int main()
{
int i,j,n;
while(n!=-1)
{
cin>>n;

for(i=0;i<=n;i++)
{
if(i==0)a[i]=0;
if(i!=0)
{
a[i]=a[i-1]-i;
if(a[i]<=0)a[i]=a[i-1]+i;
for(j=0;j<i;j++)
if(a[i]==a[j])a[i]=a[i-1]+i;
}
}
if(n==-1)break;
cout<<a[n]<<endl;
}

return 0;
}
我做的结果是对的,但当输入数大时(100000以上)要花十几秒等待,这显然不能接受.
我知道是算法有问题，它效率不高。我不知道的是要怎样去改。数据类型的确应该改为long,但这并没有解决问题。
请大家多多帮忙。

Answer 1

 
 
 
你的程序的确是如 xniren 所说，线性搜索消耗的时间太多。
你用的是 C++，大可利用标准库里的 set 类。
set 是用平衡二叉树实现的，所以它的添加、移除和搜索都是 O(log n) 操作，快得多：

#include <set>
#include <iostream>
using namespace std ;

int a[ 500001 ],
    m = 1;
set<int> existing;

int main( ) {
    for ( int k; cin >> k && k != -1; ) {
        for ( ; m <= k; m++ ) {
            int current = a[ m - 1 ] - m;
            if ( current <= 0 || ! existing.insert( current ).second )
                existing.insert( current += 2 * m );
            a[ m ] = current;
        }
        cout << a[ k ] << '\n';
    }
    return 0;
}

 
 
 

Answer 2

当输入的数比较大时，程序花在搜索数组A中是否存在相同数值的时间急剧增加。建议在搜索算法上多下功夫。程序中使用的如下的线性搜索算法显然是不可取的。
for(j=0;j<i;j++)
if(a[i]==a[j])a[i]=a[i-1]+i;

Answer 3

int的n能存100000以上?
还有,真的是100000以上,那么循环太多次了,这跟CPU速度有关,这得用专用计算或者服务器CPU来运行