编程论坛 → C++教室

编程思路求解

yy2222 发布于 2010-12-11 18:54， 1016 次点击

是好几题，请指导。不需要程序，只要个思路就好
1.两个 18位数的数相加，该怎么写这个函数？（目前的想法是用数组。但貌似绕进一个湾里）
2.表述不好。还是个原题吧。。
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output
Case 1:
14 1 4

Case 2:
7 1 6
3. 一只小白兔在一条开满玫瑰花的路上，寻找一朵最美的玫瑰，小白兔不能后退也没办法看到看到前面的花，她怎么才能找到一朵最美的玫瑰。（只能摘一次的，）

[ 本帖最后由 yy2222 于 2010-12-12 22:50 编辑 ]

10 回复

#2

jianghong_022010-12-11 19:05

那就好办《你要知道写程序最重要的就是你要会用流程图……流程图是最关键的……多看流程图

#3

pangding2010-12-12 01:20

这个流程图没什么用，主要是算法。

第一个，就用你说的那个方法就行。有什么困难的地方，具体说一下。
第二个，n^2的方法肯定行。虽然是道比较常规的题，但我算法不行，不知道有什么更好的方法。
第三个，是不是可以这样。摘起第一朵花，然后往后走。如果看见比这个漂亮的，就换一朵。走到最后时，手里的肯定是最漂亮的。(就是一次遍历找最大值)

#4

li_danwang2010-12-12 09:58

第一题：主要是想办法如何判断你输入的数是否是18位数字，如果不是18位，则重新输入，如果是18位，则进行相加。你可以用你输入的数字X除以10的17次方，判断余数是否为1到9的数字就OK了.

第二题：先保留.

第三题：其实这个问题与以前数组里面找最大值是一样的道理，你先设置最好的玫瑰花是第一朵，然后与第二朵比较，如果比前面一朵（也就相当第一朵）好看，则与手上第一朵替换掉，如果没手上好看，就不换，后面以此类推...

#5

wtoo20082010-12-12 16:57

为什么我不能发贴的.

#6

ljt2010-12-12 17:01

回复 4楼 li_danwang

个人觉得你第一题不可行，十的十七次方根本就不能算。还是的一位一位加，就像加法器那样，设计一个算法

#7

yy22222010-12-12 22:54

第一题，只能自己设计计算器，但脑里没个大概很迷惑。相加。
第二题。 n*2 不懂用一段不知长度的尺子，去取一段数，可以从任意的位置开始，从任意的位置结束。。取最大。。
第三题是只能摘一次，想不通。

#8

kspliusa2010-12-12 23:45

第一题：可以用string存储加数与被加数，然后按位相加，注意进位
第二题:是简单的DP问题
第三题：只摘一次表示不解！

#9

pangding2010-12-14 18:06

第二题我也觉得是动态规划问题。楼上能詳細说一下吗？只说是DP几乎是费话。

#10

BlueGuy2010-12-14 20:59

以下是引用pangding在2010-12-14 18:06:55的发言：

第二题我也觉得是动态规划问题。楼上能詳細说一下吗？只说是DP几乎是费话。

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, j;

    ThisSum = MaxSum = 0;
    for (j = 0; j < N; j++)
    {
        ThisSum += A[j];
        if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0)
             ThisSum = 0;
    }
    return MaxSum;
}

跟这个代码类似，/  你帮我证明下哈

#11

pangding2010-12-15 17:56

高手一来，问题就会顺利的解决～～

1