Главная » Дан целочисленный массив..сумму наибольшей по длине
18:56

Дан целочисленный массив..сумму наибольшей по длине


Задание:

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит сумму наибольшей по длине возрастающей последовательности подряд идущих элементов. Если таких последовательностей несколько, можно вывести любую из них. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.

Паскаль

Естественный язык

  1. const N=30; 
  2. var a: array [1..N] of integer; 
  3.     i, l, lmax, s, smax: integer; 
  4. begin
  5.   for i:=1 to N do readln(a[i]); 
  6.   ...
  7. end.

 

Объявляем массив A из 30 элементов. Объявляем целочисленные переменные i, l, lmax, s, smax.

В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й.

...

Си

 

  1. #include<stdio.h> 
  2. int main(void) {
  3.   const int N=30; 
  4.   int a[N]; 
  5.   int i, l, lmax, s, smax; 
  6.   for (i=0; i<N; i++)
  7.     scanf(″%d″, &a[i]); 
  8.   ...
  9. }

 

 

 Решение:

Обратим внимание, что нужно найти не длину, а сумму наибольшей (то есть, самой длинной!) возрастающей последовательности (то есть, такой, в которой каждый следующий элемент строго больше предыдущего).  В переменных l и s будем хранить длину и сумму текущей (рассматриваемой сейчас) последовательности, а в переменных lmax и smax – значения для наибольшей последовательности.

Решение на естественном языке. Записываем в переменную lmax начальное значение 0, в переменную l – значение 1, а в переменную smax – значение первого элемента массива. В цикле рассматриваем все элементы массива, начиная со 2-ого до 30-ого. Если очередной элемент больше предыдущего, увеличиваем переменную  l на 1, а к переменной s добавляем значение этого элемента; иначе записываем 1 в переменную l и значение этого элемента в s. После этого (в теле цикла) сравниваем l и lmax; если l > lmax (нашли новую самую длинную возрастающую цепочку), записываем значение s в smax.

Решение на Паскале. 

  1. const N=30;
  2. var a: array [1..N] of integer;
  3.     i, l, lmax, s, smax: integer;
  4. begin
  5.   for i:=1 to N do readln(a[i]);
  6.   lmax:=0; l:=1; s:=a[1];
  7.   for i:=2 to N do begin
  8.     if a[i] > a[i-1] then begin
  9.       l:=l+1; s:=s+a[i]
  10.     end
  11.     else begin
  12.       l:=1; s:=a[i]
  13.     end;  
  14.     if l > lmax then begin
  15.       lmax:=l;
  16.       smax:=s
  17.     end
  18.   end;
  19.   writeln(smax) 
  20. end.

 


Похожие материалы:
Нашли ошибку на сайте? Напишите в комментариях!
Категория: Язык программирования: Паскаль | Просмотров: 71 | Добавил: Ученик | Рейтинг: 5.0/1