Язык Паскаль. Найти наибольшую длину возрастающей подпоследовательности

 Задача. С клавиатуры вводится набор N целых чисел. Найти наибольшую длину возрастающей подпоследовательности.

Пример

N = 10

10 11 20 3 9 27 100 10 5 4

Наибольшая длина: 4

В этом ряду возрастающих подпоследовательностей две: числа 10 11 20 и 3 9 27 100. Наибольшая длина - 4, четыре числа в подпоследовательности 3 9 27 100.

Как будем решать задачу

Введем N - количество чисел в наборе.

Введем с клавиатуры первое число a и за длину возрастающей подпоследовательности возьмем k = 1. За искомую максимальную длину возьмем m = 1.

Далее в цикле для t от 2 до N:

1. введем число b
2. выполним проверку b>a, если условие истинно, то значение k увеличим на 1 (считаем длину возрастающей подпоследовательности), иначе значением k возьмем за 1 (возрастающая подпоследовательность оборвалась)
3. найдем максимальную длину m
4. значение переменной a перезапишем на значение b

Таблица выполнения алгоритма

a	b	b > a	k	k > m	m
10			1		1
11	11	11 > 10 да	2	2 > 1 да	2
20	20	20 > 11 да	3	3 > 2 да	3
3	3	3 > 20 нет	1	1 > 3 нет
9	9	9 > 3 да	2	2 > 3 нет
27	27	27 > 9 да	3	3 > 3 нет
100	100	100 > 27 да	4	4 > 3 да	4
10	10	10 > 100 нет	1	1 > 4 нет
5	5	5 > 10 нет	1	1 > 4 нет
4	4	4 > 5 нет	1	1 > 4 нет
					Вывод 4

Программа решения задачи на языке Паскаль

var a,b,k,m,t,N:integer;

begin

  readln(N);

  read(a); k:=1; m:=1;

  for t:=2 to N do

  begin

    read(b);

    if b>a then k+=1 else k:=1;

    m:=max(k,m); //функция нахождения максимума из двух значений

    a:=b;

  end;

  writeln('наибольшая длина возрастающей подпоследовательноси: ',m);

end.

Результат запуска программы

Язык Паскаль. Найти количество различных чисел в массиве из N элементов (2 способа решения)

Задача. Найти количество различных чисел в массиве из N элементов.

Как будем решать задачу (2 способа)

для хранения уникальных значений исходного массива будем использовать:

1. новый массив 
2. множество 

Способ 1

Сформируем массив a случайных чисел из диапазона от 0 до 20.

Заведем массив b и заполним все его ячейки числами -1.

Переменной j присвоим значение 0.

В цикле для k от 1 до n:

1. Присвоим флагу f значение true, это будет означать, что ячейка a[k] хранит уникальное значение, и его нет в массиве b.
2. В цикле для s от 1 до j сравним значение a[k] со значениями массива b (a[k]=b[s]), если условие верно, флагу присвоим значение false.
3. Если флаг не поменял значение true на false и хранит значение true, счетчик j увеличим на 1 и сохраним в ячейке b[j] значение a[k].

В итоге переменная j будет хранить количество измененных ячеек массива b - количество различных элементов исходного массива.

Программа решения задачи на языке Паскаль (способ 1)

const n = 10;

var a,b:array[1..n] of integer;

    k,s,j:integer;

    f:boolean;

begin

  write('Исходный массив: ');

  for k:=1 to n do

  begin

    a[k]:=random(21); write(a[k],' ');

    b[k]:=-1;

  end;

  j:=0;

  for k:=1 to n do

  begin

    f:=true; //элемента a[k] нет в массиве b

    for s:=1 to j do if a[k]=b[s] then f:=false;

    if f then begin j+=1; b[j]:=a[k]; end;

  end;

  writeln;

  write('Неповторяющиеся числа: ');

  for k:=1 to j do write(b[k],' ');

  writeln;

  writeln('Количество различных чисел: ',j);

end.

Способ 2

Заведем пустое множество m.

Сформируем массив a случайных чисел из диапазона от 0 до 20. 

В цикле для k от 1 до n:

1. если значение a[k] нет в множестве m, увеличим счетчик j на 1,
2. добавим значение a[k] в множество m.

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

В цикле  foreach k in m do (для каждого k, имеющегося в множестве m) выведем значения, сохраненные в множестве m.

Программа решения задачи на языке Паскаль (способ 2)

const n = 10;

var a:array[1..n] of integer;

    k,j:integer;

    m:set of integer;

begin

  m:=[];

  j:=0;

  write('Исходный массив: ');

  for k:=1 to n do

  begin

    a[k]:=random(21); write(a[k],' ');

    if not(a[k] in m) then j+=1; 

    m:=m+[a[k]];

  end;

  writeln;

  write('Неповторяющиеся числа: ');

 foreach k in m do write(k,' ');

  writeln;

  writeln('Количество различных чисел: ',j);

end.

Результат запуска программы

Если значительно увеличить количество элементов массива a, какая программа будет искать различные числа более эффективно (быстро)?

Язык Паскаль. Лера составляет 5-буквенные слова из букв ЛОГАРИФМ

 Задача. Лера составляет 5-буквенные слова из букв Л, О, Г, А, Р, И, Ф, М, причём никакие две гласные или две согласные не должны стоять рядом. Буквы в слове не должны повторяться. Сколько слов может составить Лера?

Так как буквы в слове не должны повторяться, значит получать слова будем перестановками букв. Ранее мы решали задачи на перестановки, например, про Магистра.

Как будем решать задачу

Заведем три символьных массива: массив гласных букв bg, массив согласных букв bs и массив всех букв c (его мы получим суммой гласных и согласных букв).

Получим 5-буквенное слово s перестановками букв массива c.

foreach x in c.Permutations(5) do 

   s := x.JoinToString; 

Заведем переменную f (флаг, тип boolean) и сохраним в ней значение true (истина) - это будет означать, что никаких рядом стоящих двух согласных или двух гласных букв в слове нет. Получим все перестановки из двух гласных букв (переменная y). Если сочетание двух гласных букв в слове s есть, присвоим флагу значение false (ложь). Так же поступим с согласными буквами. Если переменная f в итоге хранит значение true, значит слово s получено верно, счетчик искомых слов t увеличим на 1:  if f then t+=1;

Программа решения задачи на языке Паскаль

var

  c, x, y, bg, bs: array of char;

  s,d: string; t: integer; f:boolean;

begin

  c:= new char[8]; bg:= new char[3]; bs:= new char[5]; 

  bg[0]:='О'; bg[1]:='А'; bg[2]:='И';

  bs[0]:= 'Л'; bs[1]:= 'Г'; bs[2]:= 'Р'; bs[3]:= 'Ф'; bs[4]:= 'М';

  c:=bg+bs; //все буквы

  t := 0; 

  foreach x in c.Permutations(5) do 

    begin 

      s := x.JoinToString; 

      f:=true; //нет двух гласных или двух согласных рядом

      foreach y in bg.Permutations(2) do

      begin

        d:=y.JoinToString; 

        if d in s then f:=false;

      end;

     foreach y in bs.Permutations(2) do

      begin

        d:=y.JoinToString; 

        if d in s then f:=false;

      end;

      if f then t+=1;

    end;

  println('Количество слов, которые составит Лера: ',t); 

end.

Ответ: 480

Результат выполнения программы

Другие задачи на перестановки

• Задача про МАГИСТРа
• Задача про АВРОРУ
• Задача про КОТа

Сколько существует шестнадцатеричных трехзначных чисел, в которых все цифры различны и никакие две четные или две нечетные цифры не стоят рядом Читать

Настя составляет коды из букв слова НАСТЯ. Код должен состоять из 7 букв, буква Н должна встречаться в нём ровно два раза, буква А – как минимум один раз. Сколько различных кодов может составить Настя Читать

Алексей составляет 5-буквенные слова из букв М, А, Г, И, С, Т, Р. Каждую букву можно использовать не более одного раза, при этом в слове нельзя использовать более одной гласной. Сколько различных кодов может составить Алексей Читать