问题描述

集合S的定义如下:
(1) 1在S内;
(2) 如果x在集合S内，则2x+1与3x+1也在S内;
(3) 只有满足条件(1)(2)的元素在S内.

把S中的元素按递增顺序排列，请输出S中的第N个元素。

输入

本题有多组测试数据。每组测试数据一行，每行一个正整数N (1 <= N <= 100000)。

输出

对每组测试数据，在单独的一行中输出S的第N个元素。

输入样例

1
2
3
4
5
6
100
254

输出样例

1
3
4
7
9
10
418
1461

1。先判断1是否在s数组中
2.对于数组中的每一项求其2x+1与3x+1补充在数组的结尾
3.排序
4输出

s数组是固定的？还是根据输入的数据产生一个？
给个关键代码参考下

应该为空··要赋值的


[ 本帖最后由 jiangwu10057 于 2010-1-5 19:31 编辑 ]

不是很明白啊，还是要参考一下代码，就给个关于这个数组的有吗？

有点acm题目的味道，我想想

这个程序对内存和时间有没有限制？

#include <stdio.h>

int main()
{
    int s[100000], i, p2, p3, n, tmp;
    s[0] = 1;
    p2 = p3 = 0;

    for(i=1; i<100000; ++i) {
        s[i] = s[p2] * 2 + 1;
        tmp = s[p3] * 3 + 1;
        if(tmp == s[i]) {
            ++p3;
            ++p2;
        }
        else if(tmp < s[i]) {
            s[i] = tmp;
            ++p3;
        }
        else
            ++p2;
    }

    while(scanf("%d", &n))
        printf("%d\n", s[n-1]);
    return 0;
}

用链表应该不会有长度问题·了
用多少分配多少

强悍    ·简单的解决了
n的位置没赋值吧

[ 本帖最后由 jiangwu10057 于 2010-1-5 20:33 编辑 ]

这个数据量还不是太大，栈可以搞定，再大的话就得用堆动态分配才行了