2009 迅雷二笔成都站

shunzi__1984 2009-09-22 11:59:40

1. int strtol(const *num_str,char** endptr,int base);
将字符串转化为整数返回，base表示进制数（可以是16进制 10进制 8进制）,如果是0，则依照num_str的指示来决定适合的进制，串可以是正整数或负整数，要考虑溢出，正溢出返回INT_MAX,负溢出返回INT_MIN,转换过程如果遇到非法字符，则把非法字符前面的串转换成整数返回，用 endptr来返回第一个非法字符地址，如果endptr为NULL,则不用返回

3.给定一个正整数N，由1到N的连续整数组成的集合{1,2,3,...,N}拆分成两个不相交的字迹，若这两个子集的元素之和相等，则算一种成功的拆分，求出共有多少钟成功的拆分方式,N为小于一万的数，算法效率越高，得分越高。
函数原型: unsigned calc_num(unsigned N)//参数N为整数集合的最大数返回值为拆分方式的个数

备注：都不能调用C++和C的类库和库函数

...全文

1162 47 打赏收藏转发到动态举报

写回复

用AI写文章

47 条回复

切换为时间正序

请发表友善的回复…

发表回复

ljx87085210 2009-09-28

打赏
举报

关注

codeedoc 2009-09-28

打赏
举报

[Quote=引用 45 楼 lzy0001sl 的回复:]
第二题用动态规划做:
用c[k][n]表示使用1,2,3....k拼出和n的拼法种数，则有以下递推式：
c[k][n] = c[k-1][n-k] + c[k-1][n]（用k的拼法+不用k的拼法）
基础情况是c[1][1] = 1
则有如下做法:
c数组清0
c[1][1] = 1;
for( k = 2 ; k <= N ;k++ )
for( n = 1 ; n <= k*(k+1) /2 ; n++ )
c[k][n] = c[k-1][n-k] + c[k-1][n];
这样时空复杂度都是o(n^3)
可以只用两个1维数组交替递推来替代2维数组，缩小空间开销

用回溯来做复杂度是o(2^n),无论如何剪枝都是潜在的风险，实际项目开发中是尽量避免回溯的
[/Quote]

学习了！

karlfixed 2009-09-28

打赏
举报

先Mark一下

鸵鸟 2009-09-28

打赏
举报

更正一下
第一次循环 i=1，总和为0，1，2，得集合个数均为1
dp[j + 1] += dp[j], j < max, max为当前数组非0的元素的个数, 递推后得到的数组
数组 1 1 0 0 ... 0

鸵鸟 2009-09-28

打赏
举报

递推的情况
不好意思，本人最比较笨，可能说不太清楚，凑或看吧

数组 dp[i] 表示总和为i的集合总数
数组长度到 sum/2 + i 就好了，我这边懒得计算，就用 sum了

dp[j + i] += dp[j]

初始化 i=0，总和为0的集合个数为1
数组 1 0 0 0 ... 0

第一次循环 i=1，总和为0，1，2，得集合个数均为1
dp[j + 1] += dp[j], j < max, max为当前数组非0的元素的个数, 递推后得到的数组
数组 1 1 0 0 ... 0

第二次循环 i=2，总和为0，1，2，3 得集合个数均为1
dp[j + 2] += dp[j], j < max, max为当前数组非0的元素的个数, 递推后得到的数组
数组 1 1 1 1 ... 0

第三次循环 i=3，总和为0，1，2，4， 5， 6得集合个数均为1，现在总和为 3 的集合个数为 2
dp[j + 3] += dp[j], j < max, max为当前数组非0的元素的个数, 递推后得到的数组
数组 1 1 1 2 1 1 1 ... 0
dp[sum/2]/2 = dp[3]/2 = 1

以此类推
..........



    static public long getSetsNum1(int n)

    {

        /计算 总合， 如果为奇数， 返回 0

        long sum = 0;

        for (int i = 1; i <= n; ++i) sum += i;

        if ((sum & 1) == 1) return 0;



        sum >>= 1;



        //初始化数组 统计用

        //数组 dp[i] 表示 总和为i的集合总数

        //数组长度 到 sum/2 + i 就好了， 我这边懒得计算， 就用 sum了

        long N = ((n * (n + 1)) >> 1) + 2;

        long[] dp = new long[N];

        for (long i = 1; i < N; ++i) dp[i] = 0;



        //递推 BigO(N^3)

        dp[0] = 1;

        long max = 0;

        // 每次循环计算 1 ~ i 可以组成的集合的数目， 并入统计数组

        // 假设 i - 1 得到的数组 为 x1,x2, ..... xn

        // 第i 次计算， 只需要 基于 i - 1 的数组， 加上 i的情况, 就可以得到i 的统计数组

        for (long i = 1; i <= n; ++i)

        {

            // 这里剪去了集合的和超过的情况

            for (long j = max < sum ? max : sum; j >= 0; --j) dp[j + i] += dp[j];

            max += i;

        }

        //dp[i] 就存放的是总合为i 的集合总数

        return dp[sum] >> 1;

    }

鸵鸟 2009-09-28

打赏
举报

递归的方案



    //算法复杂度BigO(2^N), 比 那种 N!的递归 剪枝 逻辑上清楚很多

    //从前往后递归，对于每个数字， 都有加和不加两种情况

    static public long getSetsNum2(long sum, int i, int n)

    {

        //当前的数字总合 〉 sum 或者 已经走到 队尾，则该集合不符合要求，返回 0

        if (i > n ||sum < 0) return 0;

        // 数字总和 == sum， 集合符合要求， 返回1

        if (sum == 0) return 1;

        //递归 下一个数字

        return getSetsNum2(sum, i + 1, n) + getSetsNum2(sum - i, i + 1, n);

    }

    static public long getSetsNum2(int n)

    {

        //计算 总合， 如果为奇数， 返回 0

        long sum = 0;

        for (int i = 1; i <= n; ++i) sum += i;

        if ((sum & 1) == 1) return 0;



        sum >>= 1;

        //统计和的为 sum/2 的集合总数 ， 返回 其 1/2

        return getSetsNum2(sum, 0, n) >> 1;

    }

lzy0001sl 2009-09-28

打赏
举报

第二题用动态规划做:
用c[k][n]表示使用1,2,3....k拼出和n的拼法种数，则有以下递推式：
c[k][n] = c[k-1][n-k] + c[k-1][n]（用k的拼法+不用k的拼法）
基础情况是c[1][1] = 1
则有如下做法:
c数组清0
c[1][1] = 1;
for( k = 2 ; k <= N ;k++ )
for( n = 1 ; n <= k*(k+1) /2 ; n++ )
c[k][n] = c[k-1][n-k] + c[k-1][n];
这样时空复杂度都是o(n^3)
可以只用两个1维数组交替递推来替代2维数组，缩小空间开销

用回溯来做复杂度是o(2^n),无论如何剪枝都是潜在的风险，实际项目开发中是尽量避免回溯的

lzy0001sl 2009-09-27

打赏
举报

有那个高手解答下第二个的思路啊？

codeedoc 2009-09-27

打赏
举报

第三题给个效率比较挫的，有比较好的算法向各位请教了（上面DP的看不懂，能否稍稍讲解下？？）
#include <iostream>
using namespace std;

static int total = 0;
int set[10000] = {0};
bool deep_search(int nleft/*剩余多少没有填充*/,
int nLength,/*分成的一个棒的长度*/
int nCurMin,/*当前已经填充的最小的棒，只找最小的放，避免重复*/
int nTotalLeft,/*还剩的总大小(只算比现在填充的最小值更小的)*/
int *set/*集合*/,
int n/*集合长度*/)
{
if (nleft == 0)
return true;

if (nTotalLeft < nleft)
return false;

for (int i = 0; i < n; ++i)
{
if (set[i] == -1)
continue;

if (set[i] > nCurMin)
continue;

if (set[i] > nleft) //剪枝
continue;

int tmp = set[i]; //拿出这个来填充
set[i] = -1;
bool judge = deep_search(nleft-tmp, nLength, tmp, nTotalLeft-tmp, set, n);
if (judge) //可以成功
{
total++;
}

//回溯
set[i] = tmp;
}

return false;

}

unsigned calc_num(unsigned n)
{
int sum = n * (n + 1) / 2;
if (sum & 1) //奇数
{
return -1;
}
else
{
deep_search(sum/2, sum/2, 10002, sum, set, n);

return total/2;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int n;
while (cin >> n, n != -1)
{
memset(set, 0, sizeof(set));
for (int i = 0; i < n; ++i)
{
set[i] = n - i; //反序
}
unsigned int result = calc_num(n);
if (result == -1)
cout << "no, you can't now" << endl;
else
cout << result << endl;
}

return 0;
}

morilasi 2009-09-27

打赏
举报

第二题。。long long都溢出了，还需要做大数加法运算-_-

linlinjieconan 2009-09-27

打赏
举报

都是牛人！顶

limarine 2009-09-25

打赏
举报



class Program

{

    static public long getSetsNum1(int n)

    {

        //check total sum

        long sum = 0;

        for (int i = 1; i <= n; ++i) sum += i;

        if ((sum & 1) == 1) return 0;



        sum >>= 1;



        //inital array

        long N = ((n * (n + 1)) >> 1) + 2;

        long[] dp = new long[N];

        for (long i = 1; i < N; ++i) dp[i] = 0;



        //递推 BigO(N^3)

        dp[0] = 1;

        long max = 0;

        for (long i = 1; i <= n; ++i)

        {

            for (long j = max < sum ? max : sum; j >= 0; --j) dp[j + i] += dp[j];

            max += i;

        }

        return dp[sum] >> 1;

    }



    static public long getSetsNum2(long sum, int i, int n)

    {

        if (i > n||sum < 0) return 0;

        if (sum == 0) return 1;

        return getSetsNum2(sum, i + 1, n) + getSetsNum2(sum - i, i + 1, n);

    }

    static public long getSetsNum2(int n)

    {

        long sum = 0;

        for (int i = 1; i <= n; ++i) sum += i;

        if ((sum & 1) == 1) return 0;



        sum >>= 1;



        return getSetsNum2(sum, 0, n) >> 1;

    }

    static void Main(string[] args)

    {



        for (int i = 1; i < 22; ++i)

        {



            Console.WriteLine("n=" + i);

            Console.WriteLine(getSetsNum1(i));

            Console.WriteLine(getSetsNum2(i));

        }

        Console.ReadLine();

    }

}

wendll 2009-09-25

打赏
举报

marik

fblgzdq 2009-09-25

打赏
举报

limarine 2009-09-25

打赏
举报

完整代码



class Program

{

    static public long getSetsNum1(int n)

    {

        //check total sum

        long sum = 0;

        for (int i = 1; i <= n; ++i) sum += i;

        if ((sum & 1) == 1) return 0;



        sum >>= 1;



        //inital array

        long N = ((n * (n + 1)) >> 1) + 2;

        long[] dp = new long[N];

        for (long i = 1; i < N; ++i) dp[i] = 0;



        //递推 BigO(N^3)

        dp[0] = 1;

        long max = 0;

        for (long i = 1; i <= n; ++i)

        {

            for (long j = max < sum ? max : sum; j >= 0; --j) dp[j + i] += dp[j];

            max += i;

        }

        return dp[sum] >> 1;

    }



    static public long getSetsNum2(long sum, int i, int n)

    {

        if (i > n) return 0;

        if (sum == 0) return 1;

        return getSetsNum2(sum, i + 1, n) + getSetsNum2(sum - i, i + 1, n);

    }

    static public long getSetsNum2(int n)

    {

        long sum = 0;

        for (int i = 1; i <= n; ++i) sum += i;

        if ((sum & 1) == 1) return 0;



        sum >>= 1;



        return getSetsNum2(sum, 0, n) >> 1;

    }

    static void Main(string[] args)

    {



        for (int i = 1; i < 22; ++i)

        {



            Console.WriteLine("n=" + i);

            Console.WriteLine(getSetsNum1(i));

            Console.WriteLine(getSetsNum2(i));

        }

        Console.ReadLine();

    }

}

鸵鸟 2009-09-25

打赏
举报

for (int i = 1; i < 22; ++i)
{

Console.WriteLine("n=" + i);
Console.WriteLine(getSetsNum1(i));
Console.WriteLine(getSetsNum2(i));
}
输出
n=1
0
0
n=2
0
0
n=3
1
1
n=4
1
1
n=5
0
0
n=6
0
0
n=7
4
4
n=8
7
7
n=9
0
0
n=10
0
0
n=11
35
35
n=12
62
62
n=13
0
0
n=14
0
0
n=15
361
361
n=16
657
657
n=17
0
0
n=18
0
0
n=19
4110
4110
n=20
7636
7636
n=21
0
0

鸵鸟 2009-09-25

打赏
举报

static public long getSetsNum1(int n)
{
//check total sum
long sum = 0;
for (int i = 1; i <= n; ++i) sum += i;
if ((sum & 1) == 1) return 0;

sum >>= 1;

//inital array
long N = ((n * (n + 1)) >> 1) + 2;
long[] dp = new long[N];
for (long i = 1; i < N; ++i) dp[i] = 0;

//递推 BigO(N^3)
dp[0] = 1;
long max = 0;
for (long i = 1; i <= n; ++i)
{
for (long j = max < sum ? max : sum; j >= 0; --j) dp[j + i] += dp[j];
max += i;
}
return dp[sum] >> 1;
}

static public long getSetsNum2(long sum, int i, int n)
{
if (i > n) return 0;
if (sum == 0) return 1;
return getSetsNum2(sum, i + 1, n) + getSetsNum2(sum - i,i + 1, n);
}
static public long getSetsNum2(int n)
{
long sum = 0;
for (int i = 1; i <= n; ++i) sum += i;
if ((sum & 1) == 1) return 0;

sum >>= 1;

return getSetsNum2(sum, 0, n) >> 1;
}

getSetsNum1 递推 BigO(n^3)
getSetsNum2 递归 BigO(2^n)
返回值是一样的（应该是正确的），速度第一个快很多, 不过计算到50以上int64也装不下了。。。

鸵鸟 2009-09-25

打赏
举报

static public long getSetsNum(int n)
{
//check total sum
long sum = 0;
for (int i = 1; i <= n; ++i) sum += i;
if ((sum & 1) == 1) return 0;

sum >>= 1;

//inital array
long N = ((n * (n + 1)) >> 1) + 2;
long[] dp = new long[N];
for (long i = 1; i < N; ++i) dp[i] = 0;

//递推 BigO(N^3)
dp[0] = 1;
long max = 0;
for (long i = 1; i <= n; ++i)
{
for (long j = max < sum ? max : sum; j >= 0; --j) dp[j + i] += dp[j];
max += i;
}
return dp[sum] >> 1;
}

20 以内没问题， 20 以后数太大了，不知道对不对，没有正确结果验证 O(n^3)

largep 2009-09-24