2. Модельная задача Вложение управляющих структур

В заданной последовательности целых чисел найти самую длинную подпоследовательность, которая является арифметической или геометрической прогрессией.

Математическая модель

По начальным двум членам прогрессии мы определяем разность и знаменатель. Третий член определяет вид прогрессии (если она есть). Далее исследуется длина прогрессии. В случае, если очередной член последовательности не подошел, то прогрессия обрывается. При обрыве прогрессии на члене а_к, следует продолжить исследование с члена а_к-2.

Псевдокод

Работа с арифметической прогрессией

‘Установить начальные данные

ДлинMax = 0

Длин = 2

Start = 1

Цикл по последовательности чисел пока Start < N - 2

Разн = a(Start + 1) - a(Start)

Начало = Start

Цикл I по прогрессии от Start до N - 1

Если a(I + 1) = Разн + a(Start) То

Длин = Длин + 1

Начало = Начало +1

Иначе

Выход из цикла

Все Если

Все цикл

Если Длин > ДлинMax То

ДлинMax = Длин

Все Если

Start = Начало + 1

Все цикл по последовательности чисел

Программа

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Program4._2

{

class Program

{

static void Main(string[] args)

{

int N;

int[] a = new int[1000];

int MaxLong = 0, mLong, Start = 0, mBeg;

int Diff, I;

// Работа с арифметической прогрессией

Console.Write("Enter N: ");

N = Convert.ToInt32(Console.ReadLine()); // Ввод числа N - размерности массива

for (I = 0; I < N; I++)

{

Console.Write("Enter a(" + (I + 1) + "): ");

//cout<<"Enter a("<<I+1<<"): ";

a[I] = Convert.ToInt32(Console.ReadLine());

//cin>>a[I];

}

while (Start < (N - 2))

{

Diff = a[Start + 1] - a[Start]; // Разность прогрессии

mBeg = Start;

mLong = 2;

for (I = Start + 1; (I < N) && (a[I + 1] == (a[I] + Diff)); I++) /* Цикл по предполагаемой прогрессии */

{

mLong++;

mBeg++;

}

if (MaxLong < mLong)

MaxLong = mLong;

Start = mBeg + 1;

}

Console.WriteLine();

Console.WriteLine("Result:");

Console.WriteLine(MaxLong);

Console.ReadKey();

}

}

}

Аналогично решается вопрос с геометрической прогрессией.

69. Найти максимальную по длине монотонную (т. е. либо неубывающую, либо невозрастающую) подпоследовательность заданной последовательности целых чисел.

70. Определить, содержится ли в заданной последовательности целых чисел хотя бы одно число Фибоначчи.

Число a(I+2) называется числом Фибоначчи, если a(I+2) = a(I+1) + a(I)

71. Найти наименьшее общее кратное всех чисел, содержащихся в заданной последовательности натуральных чисел.

72. Проверить, является ли заданная последовательность целых чисел перестановкой начального отрезка последовательности натуральных чисел.

73. Указать длину такого начального отрезка заданной последовательности целых чисел, для которого отношение встречающихся в нем степеней двойки и чисел Фибоначчи максимально.

74. Построить последовательность длиной 100, образованную цифрами пятеричного представления последовательности натуральных чисел, начинающейся с заданного n.

75. Преобразовать заданное число из p –ичной системы счисления в q –ичную (q ≤ 16; исходное число имеет не более n знаков).