经典数据结构与算法.ppt

经典数据结构与算法?线性表?队列?堆栈?排序?查找?二叉树线性表?案例 1 Recaman 问题 Recaman's Sequence ? Time Limit: 1000ms, Special Time Limit: 2500ms, Memory Limit: 65536KB Problem 10010 : No special judgement Problem description ? 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. 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. Input ? The input consists of several test cases. Each line of the input contains an integer k where 0 <= k <= 500000. The last line contains an integer ? 1, which should not be processed. Output ? For each k given in the input, print one line containing ak to the output. Sample Input ?7 ?10000 ?-1 Sample Output ?20 ?18658 解题思路定义两个线性表:一个记录 a i的值,一个记录某个值是否已经被占用。核心代码及解释? int a[500001],b[3020000]; ?//a数组如题目描述, b数组是 Bool 数组,只有 0/1 值, 0表示没占?//用, 1表示已经被占用? int main() ?{? a[0]=0; b[]=0 ; ? for(i =1;i<500001;i++) ?{ a[i ]=a[i-1]-i; ? if(a[i ]<=0||b[a[i]]==1) ? a[i ]=a[i-1]+i; ? b[a[i ]]=1; } // 标记是否使用? while(scanf("%d",&n),n+1) ? printf("%d\n",a[n ]); ? return 0; }