时间戳

首页 > 技术文章 > 结对编程返回整数数组中最大的子数组

结对编程返回整数数组中最大的子数组

huangrb 2018-10-13 20:54 原文

 

本次作业为返回整数数组中最大的子数组，应用c++编写，在visual c++ 2010 平台执行。

在编写过程中学会以下知识：

  1. 应用 int n；int *p=new int[n]；开辟动态储存空间。满足输入动态数组的要求。
  2. 应用switch语句实现程序功能的多元化。
  3. 使用如下代码判断最大子数组之和。 for(int i=0;i<n;i++)
     {
      cin>>p[i];
     }
     int sum=p[0];
       int max_sum=p[0];
       for(int i=1;i<n;i++)
       {  
           if(sum>0)    //是否为正数
           {
               sum=sum+p[i];  //是正数，做和。
              if(sum>max_sum) // 并判断是否为最大，是让其赋值给max_sum。
                {
                    max_sum=sum;
                    end=i;
                }
           }
           else
           {
               sum=p[i];  //是负数，将第i+1个数的值赋值给和值sum
                  if(sum>max_sum)//并判断是否为最大，是让其赋值给max_sum。
                  {   
                     max_sum=sum;
                     star=i;
                     end=i;
                  }
           }
       }
       cout<<"最大子数组位置为第"<<star+1<<"个到第"<<end+1<<"个"<<endl;
       cout<<"最大子数组和为"<<max_sum<<endl;
  4. 应用p[i]=rand()输入随机数组。如果不再加任何条件时数组元素范围为零到32767 （2^16-1），其计算原理为：y＝ax＋b（mod n）其中，n一般是一个很大的素数，几万。
    a也是大素数。而且a，b，n都是常数。所以rand的产生决定于x，
    他被称为seed。
    每一个seed都是上一次产生的y的函数。这样，如果直接取seed＝y的话，
    虽然产生的rand之间相关性甚小，但只要知道某个y，就能推知以后的rand。
    为避免这种情况，一般取seed为y和当时计算机的时间的函数，如seed＝y＋t

    比如VC中对于rand()函数是如下实现的.
    int __cdecl rand (void)
    {
    return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
    }
  5. 如果想用rand函数输出负数时，可以这样应用：p[i]=-rand()%4000+2000;

源代码为：

 1 #include<iostream>
 2 #include<ctime>
 3 using namespace std;
 4 int main()
 5 {
 6     cout<<"数1601-2 20163980 \n黄瑞波"<<endl;;
 7     int m,n=0,star=0,end=0;
 8     cout<<"1.手动输入数组。\n2.随机生成数组。请选择功能：";//选择自己输入或者随机生成
 9     cin>>m;
10     switch(m)
11     {
12         case 1:{
13         int *p=new int[n];//开辟为n的存储空间
14     cout<<"请输入数组的长度：";
15     cin>>n;
16     if(n<0)
17     {
18     cout<<"输入的数组长度有误，请重新输入！"<<endl;//判断数据有效性
19     return 0;
20     }
21     cout<<"输入一个"<<n<<"维整型数组:";
22     //以下算法代码参考与网络。
23     for(int i=0;i<n;i++)
24     {
25         cin>>p[i];
26     }
27     int sum=p[0];
28    int max_sum=p[0];
29    for(int i=1;i<n;i++)
30    {   
31        if(sum>0)    //是否为正数
32        { 
33            sum=sum+p[i];  //是正数，做和。
34           if(sum>max_sum) // 并判断是否为最大，是让其赋值给max_sum。
35             { 
36                 max_sum=sum;
37                 end=i;
38             }
39        }
40        else 
41        { 
42            sum=p[i];  //是负数，将第i+1个数的值赋值给和值sum
43               if(sum>max_sum)//并判断是否为最大，是让其赋值给max_sum。
44               {    
45                  max_sum=sum;
46                  star=i;
47                  end=i;
48               }
49        }
50    }
51    cout<<"最大子数组位置为第"<<star+1<<"个到第"<<end+1<<"个"<<endl;
52    cout<<"最大子数组和为"<<max_sum<<endl;
53 };break;
54         case 2:
55             {
56                 int *p=new int[n];
57                 cout<<"请输入数组的长度：";
58         cin>>n;
59         if(n<0)
60         {
61         cout<<"输入的数组长度有误，请重新输入！"<<endl;
62         return 0;
63         }cout<<"随机数组为：";
64         for(int i=0;i<n;i++)
65     {
66         p[i]=-rand()%4000+2000;
67         cout<<p[i]<<" ";
68     }
69         cout<<endl;
70         int sum=p[0];
71    int max_sum=p[0];
72    for(int i=1;i<n;i++)
73    {   
74        if(sum>0)    //判断是否为正数
75        { 
76            sum=sum+p[i];  //是正数，做和。
77           if(sum>max_sum) // 并判断是否为最大，是让其赋值给max_sum。
78             { 
79                 max_sum=sum;
80                 end=i;
81             }
82        }
83        else 
84        { 
85            sum=p[i];  //是负数，将第i+1个数的值赋值给和值sum
86               if(sum>max_sum)//并判断是否为最大，是让其赋值给max_sum。
87               {    
88                  max_sum=sum;
89                  star=i;
90                  end=i;
91               }
92        }
93    }
94    cout<<"最大子数组位置为:第"<<star+1<<"个到第"<<end+1<<"个"<<endl;
95    cout<<"最大子数组和为:"<<max_sum<<endl;
96             };break;
97     }
98       return 0;
99 }

运行结果截图为：

 

 

 

 

推荐阅读