Задача на перестановки (Паскаль, Permutations(N))

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

Задачу на перестановки букв слова АВРОРА мы решили с использованием метода Permutations и множеств. 

В данной же задаче проблема заключается в том, что длина слова меньше, чем используемый алфавит. Будем использовать метод Permutations с аргументом N, позволяющий брать N символов из набора.

Пример:

Получим все слова из двух букв перестановками букв слова КОТ.

В массиве с сохраним буквы слова КОТ. Получим массивы перестановок функцией c.Permutations(2).

Программа на языке Паскаль

var c,x:array of char; s:string; 

begin   

    c:=new char[3];  

    c[0]:='К'; c[1]:='О'; c[2]:='Т'; 

    foreach x in c.Permutations(2) do   

     begin     

      s:=x.JoinToString;

      println(s);

     end; 

end.

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

Решим задачу про "МАГИСТРА"

Сохраним буквы М, А, Г, И, С, Т, Р в массиве c. Получим все перестановки по 5 символов циклом  foreach x in c.Permutations(5) do. Получим строку оператором s:=x.JoinToString

Если суммарное количество гласных букв ('А' и 'И') меньше или равно 1, то увеличим счетчик искомых слов t на 1.

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

var c,x:array of char; s:string; 

    t:integer;

begin   

    c:=new char[7];  

    c[0]:='М'; c[1]:='А'; c[2]:='Г'; 

    c[3]:='И'; c[4]:='С'; c[5]:='Т';

    c[6]:='Р';

    t:=0;

    foreach x in c.Permutations(5) do   

     begin     

      s:=x.JoinToString;

      if (s.CountOf('А')+s.CountOf('И'))<=1 then t+=1;

     end; 

    println(t);

end.

Ответ: 1320

Как решить задачу на перестановки (Паскаль)

Задача. Петя составляет шестибуквенные слова перестановкой букв слова АВРОРА. При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?

Мы решали задачу о перестановках букв слова КОТ. 

Данную задачу будем решать подобным образом. Но необходимо учесть, что буквы в слове повторяются (буквы А и Р), а значит, нужно исключить повторяющиеся слова.

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

Для хранения уникальных (неповторяющихся) значений можно использовать множество.

Получим строки за счет перестановок элементов символьного массива методом Permutations, исключим по условию задачи строки с двумя подряд идущими буквами А или Р и подсчитаем количество элементов полученного множества.

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

var a,x:array of char; s:string; n:set of string;      

begin   

  a:=new char[6];

  a[0]:='А';a[1]:='В';a[2]:='Р';a[3]:='О';a[4]:='Р';a[5]:='А';

  n:=[];  

  foreach x in a.Permutations do  

     begin   

     s:=x.JoinToString;   

     if not('АА' in s) and not ('РР' in s) then include(n,s);  

     end;

     println(n);

     print('Количество слов, которые составит Петя: ',n.count()); 

end.

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

Перестановки в Паскале (Permutations)

Дано слово КОТ. Получим все слова за счет перестановок с помощью программы на языке Паскаль.

Будем использовать динамический символьный массив c для хранения букв слова КОТ. С помощью метода Permutations и цикла foreach получим массивы перестановок x. Объединим элементы массива x в строку методом JoinToString и выведем строку s  на экран.

Программа на языке Паскаль

var c,x:array of char; s:string;

begin

  c:=new char[3];

  c[0]:='К'; c[1]:='О'; c[2]:='Т';

  foreach x in c.Permutations do

    begin

     s:=x.JoinToString;

     println(s);

    end;

end.

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

А если буквы в слове повторяются? Сколько различных слов можно составить из букв слова ОКНО?

Динамические массивы в Паскале (объявление, методы)

В этой публикации приведем программу, демонстрирующую некоторые возможности работы с динамическими массивами:

println count countof where sum max

min fill sort sortDescending length setLength

Для наглядности после выполнения действий будем выводить на экран массив или информацию о массиве.

Программа на языке Паскаль

var a,b:array of integer; //a и b массивы целых чисел

k:integer;

begin

  a:=new integer[20]; //выделение памяти из 20 ячеек, нумерация ячеек с 0

  println(a); //вывод массива на экран в виде списка

  a.Println; //вывод значений массива

  for k:=0 to a.Length-1 do //a.length - возвращает длину массива

    a[k]:=1+k*10;

  println(a);

  a.Where(k->k>100).Println; //вывод значений массива более 100

  a.CountOf(81).Println; //подсчет и вывод количества значений массива, равных 81

  a.Count(k->k mod 11=0).Println; //подсчет и вывод количества значений массива, кратных 11

  a.Where(k->(k mod 3=0)or(k mod 11=0)).Println; //вывод значений массива, кратных 3

  a.Sum.Println; //подсчет и вывод суммы значений массива

  a.Where(k->k mod 3=0).Sum.Println; //подсчет и вывод суммы значений массива, кратных 3

  a[0:5].println; //вывод среза массива с 0 по 4 индексы

  b:=a[:4]; //срез от начала массива до индекса 3

  b.println;

  b:=a[5:]; //срез от 5 индекса до конца массива

  b.println;

  a.Max.println; //максимум 

  a.Min.Println; //минимум

  a.SortDescending; //сортировка массива по убыванию

  a.Println;

  a.Sort(); //сортировка массива по возрастанию

  a.Println;

  setlength(a,a.length-18);//уменьшение длины массива на 18 ячеек

  a.Println;

  a.Fill(2); //заполнение массива значениями 2

  a.Println;

end.

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

Язык Паскаль. Быстрый поиск количества делителей (основная теорема арифметики)

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

Если разложение числа на простые множители представить в виде:

a = p1^s1p2^s2p3^s3…pn^sn, тогда количество делителей рассчитывается по формуле: 

(s1+1)*(s2+1)*(s3+1)*..*(sn+1)

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

Для хранения этих количеств будем использовать массив.

Программа решения задачи на языке Паскаль (эффективная)

var n, j, k: int64; d: integer; a: array of integer;

begin

  writeln('Введите число');

  readln(n);

  d := Milliseconds;

  setlength(a, 100);//кол-во возможных различных множителей

  j := 2; k := 0;

  writeln('Множители: ');

  while n > 1 do

  begin

    while n mod j = 0 do

    begin

      write(j, ' ');

      a[k] += 1;

      n := n div j;

    end;

    j := j + 1; 

    if n mod j = 0 then k += 1;

  end;

  writeln;

  //writeln('Количество множителей:');

  //a.Where(j->j<>0).Print;

  //writeln;

  writeln('Количество делителей:');

  n := 1;

  for j := 0 to k do

  begin

    if a[j] <> 0 then n := n * (a[j] + 1);

  end;

  writeln(n);

  writeln('Время: ',(Milliseconds - d) / 1000,' с');

end.

Программа решения задачи на языке Паскаль (неэффективная)

var  j, s, n, d: int64;

begin

  writeln('Введите число');

  readln(n);

  d := Milliseconds;

  s := 2;

  for j := 2 to n div 2 do

    if n mod j = 0 then s := s + 1;

  writeln('Количество делителей:');

  writeln(s);

  writeln('Время: ',(Milliseconds - d)/1000,' с');

end.

Результаты запусков

Эффективная программа

Неэффективная программа

Язык Паскаль. Как решить комбинаторную задачу про слова?

Валя составляет шестибуквенные слова из букв слова ГРОЗА. Сколько слов составит Валя, если на первом месте нельзя использовать букву З, на последнее место нельзя ставить гласные буквы, а буква Г должна встретиться в слове не более 1 раза?

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

Закодируем буквы цифрами от 1 до 5.

О – 1

А – 2

Г – 3

Р – 4

З – 5

Запустим цикл по числам n из промежутка от 111111 до 555555. Преобразуем число n в строку s процедурой str(n,s).

Выполним проверку условий:

1)      В строке есть символы ‘0’, ‘6’, ‘7’, ‘8’, ‘9’

2)      Последний символ строки – это ‘1’ или ‘2’

3)      Количество символов ‘3’ меньше или равно 1

4)      Первый символ строки – это ‘5’

Если 1-ое условие ложно и 2-ое условие ложно и 3-е условие истинно и 4-ое условие ложно, то будем увеличивать счетчик подходящих слов t на 1.

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

var n,t:integer; f1,f2,f3,f4:boolean;

    s:string;

begin

  for n:=111111 to 555555 do

  begin

    str(n,s);

    f1:=('0' in s) or ('6' in s) or ('7' in s) or ('8' in s) or ('9' in s);

    f2:=s[6] in ['1','2'];

    f3:=s.CountOf('3')<=1;

    f4:=s[1]='5';

    if (not f1) and (not f2) and f3 and (not f4) then t+=1;

  end;

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

end.

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

Данная программа нашла ответ за 1.166 с.

Как ускорить выполнение программы

Поскольку на последнем месте не может встретиться гласная буква, то есть цифры 1 и 2, то можно начать с числа 111113, на первом месте не может стоять буква З, то есть цифра 5, значит можно идти в цикле до числа 455555 и отказаться от проверки 4-ого условия.

В этом случае программа нашла ответ за 0.884 с.

Язык Паскаль. Разложение натурального числа на простые множители

Как разложить число на множители? Вспомним математику основной школы.

Выполним разложение чисел 360, 192, 36, 44 на простые множители.

В этой публикации приведем код программы для получения простых множителей некоторого натурального числа N.

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

Возьмем за первый предполагаемый множитель первое простое число j=2. Организуем внешний цикл пока число больше 1. В этом цикле организуем внутренний цикл пока число делится на j без остатка. Во внутреннем цикле будем уменьшать число в j раз и выводить множитель j на экран. Как только число перестанет делится на множитель j (перестанет работать внутренний цикл), во внешнем цикле увеличим j на 1.

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

var n,j:int64;

begin

  writeln('Введите число');

  readln(n);

  j:=2;

  while n>1 do

  begin

    while n mod j = 0 do

    begin

      writeln('Множитель ',j);

      n:=n div j;

    end;

    j:=j+1;

  end;

end.

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

Запуск 1

Запуск 2

Решето Эратосфена на языке Паскаль (поиск простых чисел быстро)

В этой публикации решим следующую задачу:

Вывести все простые числа из некоторого диапазона с использованием алгоритма "Решето Эратосфена".

Простое число - это натуральное число, имеющее ровно 2 делителя: 1 и само число. Например, 2, 3, 5, 7, 11.

Для быстрого поиска простых чисел будем использовать алгоритм "Решето Эратосфена", заключающийся в просеивании последовательности чисел так, что составные числа последовательности вычеркиваются.

Идея алгоритма

В упорядоченной последовательности натуральных чисел возьмем число k, равное 2 – первому простому числу, и вычеркнем из последовательности все числа, кратные k: 2k, 3k, 4k, …, ik (ik≤N). Далее, в качестве k возьмем следующее за 2 число – это 3, и вычеркнем все кратные 3 числа (6, 9, 12, …).

Слово "вычеркнем" следует понимать так: сделаем число нулем.

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

Последовательность натуральных чисел сохраним в массиве. Номера ячеек отождествим с числами. Ячейки с номерами 0 и 1 должны быть равны 0 (0 и 1 не являются простыми числами).

Внешний цикл запустим по k от 2 до N.

Если ячейка a[k] хранит число, не равное 0, то возьмем j=k и во внутреннем цикле пока j<=N-k, с шагом j=j+k, будем обнулять ячейку a[j].

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

var a:array of integer;

    k,j,n:integer;

begin

  {простые числа до 500}

  n:=500;

  setlength(a,n+1);

  for k:=0 to n do a[k]:=k;

  a[1]:=0;

  for k:=2 to n do

  begin

    if a[k]<>0 then  

      begin 

       j:=k;

       while (j<=n-k) do

        begin

         j:=j+k;

         a[j]:=0;

        end;

      end;

  end;

  a.Where(k->k<>0).print; {вывод элементов массива, не равных 0}

end.

Время выполнения программы

Сравним время выполнения программ для поиска простых чисел в диапазоне от 0 до 50 000 с использованием алгоритма "Решето Эратосфена" и алгоритма, в котором для каждого числа считается количество его делителей.

Решето Эратосфена

Подсчет количества делителей

var a:array of integer;     k,j,n:integer; begin   var d := Milliseconds;   {простые числа до 50000}   n:=50000;   setlength(a,n+1);   for k:=0 to n do a[k]:=k;   a[1]:=0;   for k:=2 to n do   begin     if a[k]<>0 then         begin         j:=k;        while (j<=n-k) do         begin          j:=j+k;          a[j]:=0;         end;       end;    end;  // a.Where(k->k<>0).print;   println;   println((Milliseconds-d)/1000); end. Время: 0.041 с

var a:array of integer;     k,j,n,p:integer; begin   var d := Milliseconds;   {простые числа до 50000}   n:=50000;   setlength(a,n+1);   for k:=0 to n do a[k]:=0;   a[1]:=0;   for k:=2 to n do   begin     p:=0;     for j:=1 to k div 2 do       if k mod j=0 then p+=1;     if p=1 then a[k]:=k;   end;   //a.Where(k->k<>0).print;   println;   println((Milliseconds-d)/1000); end. Время: 10.894 с

Очевидно, что программа "Решето Эратосфена" ищет простые числа быстрее.

Для промежутка чисел [0; 100 000] время выполнения программы составило 0.096 с; программа, подсчитывающая количество делителей, выполнилась за 46.2 с.

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

Таблица простых чисел до 200

Функции count и countof в языке Паскаль (примеры использования в задачах)

Для подсчета количества каких-либо символов, имеющихся в строке, можно использовать функции:

• countof
• count

В чем разница этих функций, и как их применить к решению задач, разберём в этой публикации.

Функция countof

Пусть дана строка

s:='231привет2432';

Вычислим количество цифр '2':

d:=s.countof('2');

Функция s.countof('2') подсчитывает количество цифр 2 в строке s, и в качестве своего аргумента использует символ 2, заключенный в апострофы.

Пример задачи 1

С клавиатуры вводится строка. Найти количество символов 'Z'.

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

var s:string;k:integer;

begin

  readln(s);

  k:=s.Countof('Z');

  println(k);

end.

Пример задачи 2

С клавиатуры вводится строка. Верно ли, что строка содержит символ '9'?

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

var s:string;k:integer;

begin

  readln(s);

  k:=s.Countof('9');

  if k>0 then writeln('Строка содержит цифру 9')

         else writeln('В строке нет цифр 9');

end.

Функция count

Пусть дана строка

s:='flower555';

Вычислим количество цифр '5':

d:=s.count(c->c='5');

Функция s.count(c->c='5') в качестве своего аргумента принимает логическое выражение (условие). Переменная c в данном случае должна быть описана типом char в блоке var.

Преимуществом функции count перед функцией countof можно считать возможность применения сложных условий.

Пример задачи 1

С клавиатуры вводится строка. Найти количество символов 'Z' и 'A'.

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

var s:string;c:char;k:integer;

begin

  readln(s);

  k:=s.Count(c->(c='Z')or(c<='A'));

  println(k);

end.

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

Пример задачи 2

С клавиатуры вводится строка. Найти количество символов цифр.

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

var s:string;c:char;k:integer;

begin

  readln(s);

  k:=s.Count(c->(c>='0')and(c<='9'));

  println(k);

end.

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

Пример задачи 3

Во введенной строке подсчитать все символы, кроме P.

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

var s:string;k:integer;c:char;

begin

  readln(s);

  k:=s.Count(c->not(c='P'));

  println(k);

end.

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