Файл: Reshenie_algoritmicheskikh_zadach_2011.pdf

1.Найти хотя бы один набор десятичных значащих цифр А, Б, В, Г при условии, что выполнено равенство АБАВ+БАБ2=ГГВ1.

Указание: заметим, что В=9 так как в этом разряде суммы стоит цифра 1, которая может получиться лишь при сложении 2 с 9; продолжить аналогичные рассуждения относительно остальных разрядов.

2.Найдите все возможные подходящие варианты наборов цифр для равенства вида: ABCD + ECDF = A000C, где каждой букве соответствует одна десятичная цифра (разным буквам – разные цифры) и перенос из младшего разряд был. Указание: заметим, что А=1 так как при сложении старших разрядов слагаемых может переноситься в следующий разряд лишь 1; продолжить аналогичные рассуждения относительно остальных разрядов.

3.X, Y, Z, U, V должны поехать в разные города А, Б, В, Г, Д, Е. X может ехать только в А, Б, Д; Y может ехать только в А, Б и В; Z может ехать только в В; U не может ехать никуда, куда может ехать Y; V не может ехать только Д и Е. Необходимо определить, в каком городе мог быть каждый из них, если оказалось, что вдвоем они не были ни в одном городе. Указание: сделать таблицу возможностей поездок, строки которой пометить именами, а столбцы –городами.

4.Если из четырех лекций в расписании занятий за математикой может следовать любая дисциплина, информатика может следовать только за математикой, а английский язык — только за информатикой, то какой по счету лекцией может быть история? Определить за минимум рассуждений. Одно рассуждение – простое высказывание относительно одного из перечисленных предметов. Указание: рассмотреть два возможных "претендента на первый урок".

5.Студент А — отличник, у Б — пятерка или четверки, у В и Д — четверки или тройки, у Г — возможны все оценки. Какие оценки у каждого из них по контрольной работе, если все они получили различные оценки?

6.Андрей не может ехать в Малайзию и Китай. Николай хочет ехать только в Малайзию или Румынию. Геннадий не хочет ехать только в Уругвай. Сергей согласен ехать лишь в Румынию и Того, а Владимир может поехать в любую страну, кроме Китая, Уругвая и Того. Может ли каждый в одиночестве посетить одну из названных стран?

7.Найти одну фальшивую, более тяжелую монету из 257 монет, используя лишь рычажные чашечные весы за минимум взвешиваний. Сколько можно добавить к этим монетам еще одинакового веса монет, чтобы это количество взвешиваний не изменилось.

8.Андрей и Петр — родственники Евгения, Дмитрий — родственник Николая и Петра. Кому должен приходиться родственником Николай, чтобы они все были родственниками друг другу?

9.Имеются только вагоны вместимости 23 тонны и 37 тонн. Поезд из полностью загруженных вагонов с грузом в 883 тонны прибыл на станцию расцепления. Здесь из его вагонов сформировали и отправили поезд с 379 тоннами груза (без перегрузки и добавления других вагонов). Сколько вагонов каждой вместимости осталось в исходном поезде на станции расцепления? Ответ обосновать минимумом кратких и утвердительных рассуждений.

; начните с наименьшего возможного значения x (почему?).

10.Обсуждая свои возможности по поступлению в вуз абитуриенты Андрей, Борис и Владимир высказали следующие предположения (в виде сложного высказывания, состоящего из двух простых высказываний) вида: Андрей — "Я не смогу поступить, а Владимир

— поступит"; Борис — "Владимир не поступит, а Андрей — поступит"; Владимир — "Если я поступлю, то Борис — не поступит или наоборот". После сдачи экзаменов выяснилось, что каждый высказал одно верное и одно ложное простое утверждение. а) Кто поступил в вуз, если не смог поступить лишь один из них? б) Кто поступил в вуз, если поступил лишь один из них?

Построение алгоритмов

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

Указание: выделять цифры числа с младшего разряда, используя функции целочисленного деления и остатка.

2.Составить алгоритм нахождения частного от факториалов двух заданных натуральных чисел.

Указание: вычислите факториал от меньшего числа и из него получите факториал большего числа; отметим, что математически более грамотно вначале сократить эту дробь.

3.Составить алгоритм поиска суммы и произведения всех простых чисел до заданного натурального числа.

Указание: простое число не имеет делителей, кроме 1 и себя; можно просто проверить кратность текущего числа n всем натуральным числам от 2 до int(n/2) (более точная верхняя граница – sqrt(n)).

4.Составить алгоритм перевода заданного двоичного натурального числа в десятичную систему.

Указание: очередную степень двойки лучше получать из предыдущей (умножением или сложением).

5.Составить алгоритм перевода заданного натурального числа в двоичную систему.

Указание: использовать функции целочисленного деления и остатка.

1.Составить алгоритм нахождения наибольшего в первой половине и наименьшего во второй половине элементов для заданного ряда вещественных чисел.

Указание: оба элемента находить в одном и том же цикле от 1 до int(n/2) – один с начала, другой – с конца.

2.Составить алгоритм суммирования всех чисел, превышающих среднее арифметическое заданного ряда вещественных чисел.

Указание: сначала найти среднее арифметическое элементов ряда.

3.Составить алгоритм нахождения произведения всех чисел, превышающих среднее геометрическое заданного ряда вещественных чисел.

Указание: сначала найти среднее геометрическое элементов ряда – оно равно корню степени n от произведения таких чисел, где n – количество таких чисел.

4.Составить алгоритм нахождения суммы всех положительных элементов и произведения всех отрицательных элементов заданной произвольной матрицы вещественных чисел.

Указание: организовать вложенные друг в друга два цикла для просмотра элементов матрицы – внешний цикл по строкам и внутренний цикл по столбцам (можно и наоборот).

5.Составить алгоритм нахождения количества слов начинающихся и заканчивающихся на заданные символы в заданном тексте и длины не более 255 символов. Слова разделены лишь одним пробелом.

Указание: выделять слова можно, проверяя наличие в конце подтекста пробела; лучше добавить к тексту один пробел искусственно, чтобы эта процедура работала и для последнего слова текста.

Рекурсия

Игру «Ханойские башни», придумал в 1883 году Эдуард Люка.

Есть три стержня и 64 кольца, нанизанных на них. В начале все кольца находятся на первом стержне, причѐм все кольца разного диаметра, и меньшие кольца лежат на больших. За ход разрешается взять верхнее кольцо с любого стержня и положить на другой стержень сверху, при этом запрещается класть большее кольцо на меньшее. Цель игры состоит в том, чтобы переместить всю пирамиду с первого стержня на второй.

Алгоритм, записанный на псевдокоде, реализует рекурсивную идею перемещения колец в игре «Ханойские башни». Функция MOVE(n,x,y) перемещает n колец со стержня с номером x на стержень с номером y.

function move(n,x,y) if n=1 then

передвинуть кольцо с стержня x на стержень y

end if

move (n-1,x,6-x-y) move (1,x,y)

move (n-1,6-x-y,y) end function

function move(n,x,y) if n=1 then

передвинуть кольцо с стержня x на стержень y

end if

move (n-1,x,6-x-y) move (1,x,y)

move (n-1,6-x-y,y) end function

Продолжите последовательность вызовов функции для пирамиды из 4 колец:

move (4,1,2)-> move (3,1,3) -> move (2,1,2) -> move (1,1,3) -> move (1,1,2) -> move (2,1,2)->

Изобразите решение в Power Point.