C语言连续子向量的最大和及时间度量实例

本文实例分析了C语言连续子向量的最大和及时间度量,分享给大家供大家参考之用。具体方法如下:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SCALE 3000
int maxnum(int a, int b);
int main(int argc, char const *argv[])
{
 FILE *fp;
 fp = fopen("maximum.in", "r");
 // int x[] = {1,12,-11,10,-65,54,22,-9,21,5,48,5,-8,-2,56,54,-88,-5,2,-8,554,-56,35,-55,555,-65,-545,-23,48,-5,88,-56,16,-8};
 int *x = (int *)malloc(sizeof(int)*(SCALE+1));
 int xi = SCALE,a = 0,num_in = 0;
 while(xi--){
  fscanf(fp, "%d", &x[a++]);
 }
 clock_t start, end;

 // ***Algorithm-1 cube***
 start = clock();

 int max = 0;
 int length = SCALE;
 int i,j,k;
 for (i = 0; i < length; ++i)
 {
  for (j = i; j < length; ++j)
  {
   int sum = 0;
   for (k = i; k <= j; ++k)
   {
    sum += x[k];
   }
   max = maxnum(max, sum);
  }
 }

 // long num = 10000000L;
 // while(num--);

 end = clock();
 double times = (double)(end - start)/CLOCKS_PER_SEC;
 double dend = (double)end;
 printf("\n***Algorithm-1 cube***\n");
 printf("end: %f\n", dend);
 printf("Time consuming: %f\n", times);
 printf("%d\n", max);
 // ***Algorithm-2 square***
 start = clock();
 max = 0;
 for (i = 0; i < length; ++i)
 {
  int sum = 0;
  for (j = i; j < length; ++j)
  {
   sum += x[j];
   max = maxnum(max, sum);
  }
 }
 end = clock();
 times = (double)(end - start)/CLOCKS_PER_SEC;
 dend = (double)end;
 printf("\n***Algorithm-2 square***\n");
 printf("end: %f\n", dend);
 printf("Time consuming: %f\n", times);
 printf("%d\n", max);
 // ***Algorithm-3 linear***
 start = clock();
 max = 0;
 int max_end_here = 0;

 for (i = 0; i < length; ++i)
 {
  max_end_here = maxnum(max_end_here + x[i], 0);
  max = maxnum(max, max_end_here);
 }
 end = clock();
 times = (double)(end - start)/CLOCKS_PER_SEC;
 dend = (double)end;
 printf("\n***Algorithm-3 linear***\n");
 printf("end: %f\n", dend);
 printf("Time consuming: %f\n", times);
 printf("%d\n", max);
 free(x);
 x = NULL;
 return 0;
}
int maxnum(int a, int b)
{
 return a > b ? a : b;
}

感兴趣的朋友可以测试运行一下本文实例以加深理解。希望本文所述对大家C程序设计的学习有所帮助。

(0)

相关推荐

  • C语言求向量和的两则问题解答分享

    求一个向量的任何连续子向量的最大和 比如向量(31,-41,59,26,-53,58,97,-93,-23,84); 最大和是从59到97即为187 #include<stdio.h> #include<stdlib.h> //两者的最大值 int max( int x, int y ); //三者的最大值 int max2( int x, int y, int z ); //最原始的算法,复杂度为T(n)=O(n*n) int oringinal( int v[], int le

  • C语言连续子向量的最大和及时间度量实例

    本文实例分析了C语言连续子向量的最大和及时间度量,分享给大家供大家参考之用.具体方法如下: #include <stdio.h> #include <time.h> #include <stdlib.h> #define SCALE 3000 int maxnum(int a, int b); int main(int argc, char const *argv[]) { FILE *fp; fp = fopen("maximum.in", &qu

  • Python语言描述连续子数组的最大和

    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住?(子向量的长度至少是1) 思路: 最大和连续子数组一定有如下几个特点: 1.第一个不为负数 2.如果前面数的累加值

  • C语言连续生成随机数的实现方法

    srand()设置随机数种子 rand()生成0 - RAND_MAX范围的随机数 加上其他运算,我们能够生成任意范围的随机数 .rand()是将随机数表里面的随机数顺序输出.所以,如果不设定随机数种子,生成的随机数是固定的. int main() { char str[10] = {0}; int j =0; while(j < 10) {//生成随机的三个数字 int i = strlen(str); for (;i < 3;i++){ str[i] = '0' + rand() % 10

  • C语言连续生成多个随机数实现可限制范围

    生成随机数 在现实中我们经常用到随机数,可怎么实现呢,且听小乔慢慢道来. 在C语言中,我们一般使用 <stdlib.h> 头文件中的 rand() 函数来生成随机数 int void rand() 可是却发现生成的数字都一样. 这是因为rand() 函数产生的随机数是伪随机数,是根据一个数值按照某个公式推算出来的,而这个数值由一个公式计算得来,这个值在电脑启动后是不变的.在这里我将这个公式比作一个种子,现在我们就要修改这个种子. 常用的方法是用 srand 修改种子. srand用法 void

  • C语言中栈和队列实现表达式求值的实例

    C语言中栈和队列实现表达式求值的实例 实现代码: #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 typedef int Status; typedef char StackElemtype; typedef struct Stack{ StackElemty

  • C语言中实现“17进制”转“10进制”实例代码

    C语言中实现"17进制"转"10进制"实例代码 17进制转成10进制,输入是数字跟大写字母.例如输入G.11.FF,分别输出16.18.270 #include <iostream> #include <string> using namespace std; int main() { string s; int len,factor=17,num; bool sign;//用来标志输入字符串是否非法 while(cin>>s)

  • C语言实现斐波那契数列(非递归)的实例讲解

    废话不多说,直接上代码 #include <stdio.h> #include <stdlib.h> void f(int n); int main(void) { f(10); return 0; } void f(int n) { if(n==1) { printf("1\n"); return; } if(n==2) { printf("1 1\n"); return; } printf("1 1 "); int*

  • C语言练习题:求1到10的阶乘之和简单实例

    C语言练习题:求1到10的阶乘之和简单实例 #include <stdio.h> int factorial(int n) { if(0==n) return 1; if(1==n) return 1; return n*factorial(n-1); } int main() { int n=10; int sum=0; int i; for(i=1;i<=n;i++){ int m=factorial(i); printf("%d->%d\n",i,m);

  • 详解C语言用malloc函数申请二维动态数组的实例

    详解C语言用malloc函数申请二维动态数组的实例 C语言在程序运行中动态的申请及释放内存十分方便,一维数组的申请及释放比较简单. Sample one #include <stdio.h> int main() { char * p=(char *)malloc(sizeof(char)*5);//申请包含5个字符型的数组 free(p); return 0; } 是否申请二维动态内存也如此简单呢?答案是否定的.申请二维数组有一下几种方法 Sample two /* 申请一个5行3列的字符型

  • C语言输入三角形边长判断其类型并输出面积实例代码

    本文主要研究的是输入三角形边长判断其类型并输出面积,用C语言实现,具体如下. 思路:首先判断所给的三条边是否能够组成三角形,若可以组成三角形,则判断该三角形是什么类型,并求三角形的面积. 相关知识: 三角形是由同一平面内不在同一直线上的三条线段'首尾'顺次连接所组成的封闭图形.常见的三角形按边分有普通三角形(三条边都不相等),等腰三角(腰与底不等的等腰三角形.腰与底相等的等腰三角形即等边三角形) 不等边三角形:不等边三角形,数学定义,指的是三条边都不相等的三角形叫不等边三角形. 等腰三角形:等腰

随机推荐