题目:
    1.数组a中存放K个整数的序列{N1,N2,…,Nk,},其任意连续子序列可表示为{Ni,N[size=1]i+1[/size],…,Nj,},其中1<=i<=j<=K.最大连续子序列是所有连续子序列中元素和最大的一个.例如给定序列{-2,11,-4,13,-5,-2},其最大连续子序列为{11,-4,13},最大和为20,子序列长度为3.
[bo]问题: 编写函数maxsubstr,其功能是求最大连续子序列的最大和，以及最大连续子序列的长度，函数的返回值表示求得的最大和。[/bo]


    2.为便于描述屏幕上每个像素的位置,在屏幕上建立平面直角坐标系。屏幕左上角的像素设为原点，水平向右方向设为x轴，垂直向下方向设为y轴。
    设某种显示器的像素有128*128，即在每条水平线和垂直线上都有128个像素。这样，屏幕上的每个像素可用坐标（x，y）来描述其位置，其中x和y都是整数，0<=x<=127,0<=y<=127。
   现用一维数组MAP来存储整个一屏显示的位图信息。数组的每个元素有16位二进制，其中每位对应一个像素，“1”表示该像素“亮”，“0”表示该像素“暗”。数组MAP的各个元素与屏幕上的像素对应后，其位置可排列如下：
MAP(0)，MAP(1)，……，MAP(7)
MAP(8)，MAP(9)，……，MAP(15)
……
MAP(1016)，MAP(1017)，……，MAP(1023)
   [bo]问题: 根据以上描述，写一函数int SetPixel(unsigned short MAP[],int x,int y,int v);用来将指定坐标（x,y）上的像素置为“亮”（v=1）或“暗”（v=0）。函数的返回值表示操作的成功与否，取值有下面三种：
a)    返回0，表示成功；
b)    返回1，表示出错，因为v值不合法；
c)    返回2 ，表示出错，因为点（x，y）不在屏幕范围内。[/bo]


    3.假设用链表表示八进制，如八进制数536被表示为如下链表：
Q->[un]5| [/un]->[un]3| [/un]->[un]6|^[/un]
要求编写函数Add，它有两个参数P和Q，分别指向两个链表（表示两个八进制）。调用函数Add（P，Q）后将返回链表R，R是表示P八进制加上Q八进制后所得的八进制数的链表。例如，再有P如下：
P->[un]7| [/un]->[un]2| [/un]->[un]4| [/un]->[un]3|^ [/un]
则执行Add（P，Q）结果应如下（注：0536+07243=010001）：
R->[un]1| [/un]->[un]0| [/un]->[un]0| [/un]->[un]0| [/un]->[un]1|^[/un]


谢谢!

[[it] 本帖最后由 妍清舞 于 2008-3-5 18:03 编辑 [/it]]

#include<stdio.h>
#include<stdlib.h>
#define N 6
int main()
{ void maxsubstr(int a[N]);
  int a[N],i;
  for(i=0;i<N;i++)
    scanf("%d",&a[i]);
  maxsubstr(a);
  return 0;
}

void maxsubstr(int a[N])
{  int temp,max,x,y,q;
   temp=0;
   max=a[0];
   for(x=0;x<N;x++)
     {
     for(y=x;y<N;y++)
       {
       temp=temp+a[y];
       if(temp>max)
       {max=temp;
        q=y-x+1;}
        }      
       temp=0;
     }
       printf("max is %d\n",max);
       printf("max substr is %d",q);
      
       system("pause");

}

[[it] 本帖最后由 有敌手 于 2008-3-5 19:15 编辑 [/it]]

a)    返回0，表示成功；
b)    返回1，表示出错，因为v值不合法；
c)    返回2 ，表示出错，因为点（x，y）不在屏幕范围内。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝
第二个题不是很理解。。。
因为这三个来说实在是很简单。。。
b）直接检查V值就可以了。。
c）直接检查x，y值就可以了。。。。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝
我小白，说错了请不要BS我。。。

呵呵,高手谦虚了,虽然只提供其中一部分,不过依然谢谢!

#include <stdio.h>

#define K 6

int maxsubstr(int source[], int source_len, int *max_idx, int *max_len);

int main(void)
{
    int source[K] = {-2,11,-4,13,-5,-2};
    int sum = 0;
    int idx = 0;
    int length = 1;
    int i;

    sum = maxsubstr(source, K, &idx, &length);
   
    printf("the sourcestr: [");
    for (i=0; i<K; ++i)
    {
        if (i != 0)
        {
            putchar(',');
        }
        printf("%d", source[i]);
    }
    printf("]\n");
   
    printf("the maxsubstr: [");
    for (i=idx; i<idx+length; ++i)
    {
        if (i != idx)
        {
            putchar(',');
        }
        printf("%d", source[i]);
    }
    printf("]\n");
    printf("sum: %d\nlength: %d\n", sum, length);
   
    return 0;
}

int maxsubstr(int source[], int source_len, int *max_idx, int *max_len)
{
    int i,j;
    int sum = 0;
    int max_sum = 0;
    *max_idx = 0;
    *max_len = 1;

    for (i=0; i<source_len; ++i)
    {
        sum = 0;
        for (j=i; j<source_len-i; ++j)
        {
            sum += source[j];
            if (sum > max_sum)
            {
                max_sum = sum;
                *max_idx = i;
                *max_len = j - i + 1;
            }
        }
        
    }

    return max_sum;
}


运行结果如下：

E:\_work_\c>a
the sourcestr: [-2,11,-4,13,-5,-2]
the maxsubstr: [11,-4,13]
sum: 20
length: 3

[[it] 本帖最后由 netsolo 于 2008-3-6 12:32 编辑 [/it]]

第三个问题，给出的数据结构很别扭，而且函数格式还限定死了

[[it] 本帖最后由 netsolo 于 2008-3-6 13:36 编辑 [/it]]

那具体该如何实现呢?  假设已经对P,Q链表进行了倒序,即:
P->3| ->4| ->2| ->7|^
Q->5| ->3| ->6|^
谢谢!

第一题是算法中的最大子段和。我上次已经回复过另一个帖子提到了。在各种算法书中都可以找到。最佳解的时间复杂度是O（n）：
（动态规划算法：）
返回最大子段和：   n：数组元素个数。a： 数组地址
int maxsubstr(int n, int *a)
{
    int sum=0, i,b=0;
    for(i=0;i<n;i++)
    {
        if(b>0)
            b+=a[i];
        else
            b=a[i];
        if(b>sum)
            sum=b;
    }
    return sum;
}

void main()
{
    int a[]={-2,11,-4,13,-5,-2};
    int sum=maxsubstr(sizeof a / sizeof a[0],a);
    printf("sum=%d\n",sum);
}

[[it] 本帖最后由 hoodlum1980 于 2008-3-17 14:26 编辑 [/it]]

输出最大子段的起始区间和最大和。

#include <stdio.h>
int maxsubstr(int n, int *a, int *start, int *end)
{
    int sum=0, i,b=0,b_negative=1;
    *start=0;
    for(i=0;i<n;i++)
    {
        b= b>0? (a[i]+b) : a[i];
        if(b>sum)
        {
            sum=b;
            *end=i;       /* 记录结束点 */
        }
        if(b_negative && b>=0)
            *start=i;     /* 如果b从负数变为正数，则更新子段起始点 */
        b_negative=b<0? 1:0;   /* 设置b是否为负数的标记 */
    }
    return sum;
}

void main()
{
     int a[]={-2,80,-40,-50,45,20,21,-25,30,2};
     int start,end;
     int sum=maxsubstr(sizeof a / sizeof a[0],a,&start,&end);
     printf("\nsum[%d, %d]=%d\n",start,end,sum);
}

[[it] 本帖最后由 hoodlum1980 于 2008-3-17 15:17 编辑 [/it]]

我只看了求sum的逻辑,是正确的，时间复杂度O(n^2);