Лабораторная работа 2. Переборные задачи. Тексты всех программ должны быть в конспекте. При защите работы нужно уметь ответить на вопросы по этим программам.
Задача 1. Задача “3Х+1” . Возьмём какое-нибудь натуральное число. Далее, если число чётное, разделим его на 2, а если нечётное – умножим на 3 и прибавим 1. Затем будем выполнять эти действия с полученным числом. Например, вот что будет происходить, если начать с тройки. 3–>3*3+1=10–>10/2=5 –>3*5+1=16 –>16/2=8 –> 8/2=4 –>4/2=2 –> 2/2=1 –>1*3+1=4 Круг замкнулся. Теперь мы будем постоянно получать значения 1 – 4 – 2. Требуется найти такое число, которое в конце преобразований не придёт к единице. Математика бьётся над решением этой задачи более 70 лет без успеха, не смотря на объявленную за её решение премию в 1000000$.
Задание 1а. Написать программу, которая производила бы числа по приведённому закону.
Начинается программа стандартно: приглашением пользователя ввести начальное число.
10 PRINT “ENTER A NUMBER”
20 INPUT N
Теперь в зависимости от чётности числа N его нужно или разделить на 2, или умножить на 3 и прибавить 1. Проверка чётности выражением N MOD 2 в данной версии бейсика работает корректно только для чисел, меньших 215, поэтому в качестве условия чётности используем другое выражение. Для чётного числа N его половина – целое число. Поэтому будет выполняться равенство N/2=INT(N/2). Здесь функция INT(X) возвращает целую часть числа X (от англ. integer – целый). Пишем третью строку
30 IF N/2=INT(N/2) THEN N=N/2 ELSE N=3*N+1
40 PRINT N
Теперь, если мы не достигли единицы, операцию нужно провести ещё раз. Пятая строка:
50 IF N<>1 THEN GOTO 30
Программа готова.
Задание 1б. Видоизменить программу так, чтобы она подсчитывала количество шагов, которое требуется для достижении единицы.
Для этого введём переменную T и будем увеличивать её на 1 каждый раз, когда значение N изменяется.
При видоизменении программ в полной мере ощущается удобство нумерации строк через 10. Чтобы задать начальное значение Т пишем:
25 T=0
Увеличение T должно происходиь после строки 30, поэтому пишем:
35 T=T+1
В конце работы программы печатаем полученное значение T
60 PRINT “STEPS: “;T
Задание 1в. Найдите с помощью полученной программы числа из первой сотни, которые приходят к единице дольше чем за 100 шагов. Какое число, большее 1000 придёт к единице быстрее всего?
Задание 1г. Видоизмените программу так, чтобы выводила в конце работы и пиковое значение N. Подсказка: понадобится ещё одна переменная, фиксирующая максимумы, Подмайте, в каком случае её значение должно изменяться.
Задание 1д. Найдите, какой самый высокий пик достигается числами из первой сотни? Из первых 200?
Задача 2. Проверка простоты числа. Простым числом называется такое число, которое имеет ровно два делителя: самого себя и единицу. Требуется для данного числа указать, является ли оно простым.
Задание 2а. Решить задачу полной проверкой делимости на все числа, меньшие N, «в лоб».
10 PRINT “ENTER A NUMBER”
20 INPUT N#
Здесь обозначение N# обозначает, что мы сможем работать с числами длиной до 16 знаков.
30 D#=1
40 D#=D#+1
Переменная D# будет пробегать значения всех чисел, меньших N#. Далее находим частное от деления N# на D# и для контроля работы программы выводим его на экран:
50 K#=N#/D#
60 PRINT N#;”/”;D#;”=”;K#
Если частное окажется целым, N# – составное число и перебор можно заканчивать.
70 IF K#=INT(K#) THEN PRINT N#; “ DIVIDES BY ”;D#: END
Здесь мы впервые используем двоеточие – для вывода несокльких операторов в одной строке.
Если делитель до сих пор меньше N#, его нужно увеличить на единицу и продолжить проверку
80 IF D#
Если же мы перебрали все числа и не нашли делителя, то число N# – простое
90 PRINT N#; “ IS PRIME”
Задание 2б. Найдите с помощью этой программы несколько номеров ближайших и прошедших лет, которые бли простыми числами
Задание 2в. Усовершенствуйте программу так, чтобы она перебирала делители быстрее. Подсказка: стоит ли продолжать перебор, если частное K оказывается меньше делителя D#? Для дополнительного увеличения быстробействия потребуется убрать вывод на экран промежуточных результатов. Для этого наберите на пустой строке номер строки, которую нужно удалить и нажмите Enter
Задание 2г. Проверьте с помощью усовершенствованной программы на простоту числа: 12659363, 2147483647, 514229, 344805047, 469718941, 87178291199, 99999900001, 1073676287, 7599983.
Задача 3. Подсчёт числа счастливых билетов. Номер автобусного билета состоит из 6 цифр: ABCDEF. Билет называется счастливым, если сумма первых трёх цифр равна сумме последних трёх: A+B+C=D+E+F.
Задание 3а. Написать программу, подсчитывающую число таких билетов.
Для нахождения общего количества таких билетов пробежим все 6-ти значные номера и проверим каждый на выполнение условия.
10 S=0
Переменная S будет хранить количество найденных билетов. Затем каждая из цифр пробегает от 0 до 9:
20 FOR A=0 TO 9
30 FOR B=0 TO 9
40 FOR C=0 TO 9
50 FOR D=0 TO 9
60 FOR E=0 TO 9
70 FOR F=0 TO 9
Чтобы быстро ввести данные 6 строк, вводим строку 20, нажимаем Enter. Затем поднимаемся к ней курсором, меняем 2 на 3 и A на B, снова нажимаем Enter. Затем меняем 3 на 4 и B на C и снова нажимаем Enter, и т.д. В результате в памяти компьютера останутся все 6 строк. Это можно проверить, вызвав полный текст программы на экран командой LIST.
80 IF A+B+C=D+E+F THEN S=S+1
Если выполняется условие равенства сумм, переменная S увеличивается на 1. Теперь закрываем циклы, это можно сделать одной строкой:
90 NEXT F,E,D,C,B,A
И выводим на экран результат:
100 PRINT S
Задание 3б. Билет называется весёлым, если суммы первых и последних трёх цифр различаются на 1. Напишите программу для подсчёта количества весёлых билетов.
Мы всё так же будем пробегать все номера билетов, изменится лишь строка 80 – условие увеличения переменной S. Вместо A+B+C=D+E+F можем записать A+B+C-D-E-F=1 OR A+B+C-D-E-F=-1. Можем сделать это короче, использовав модуль числа, функцию ABS (от англ. absolute - абсолютный).
80 IF ABS(A+B+C-D-E-F)=1 THEN S=S+1
Задание 3в. Найдите количество билетов, у которых произведение первых трёх цифр равно произведению последних трёх.
Задание 3г. Найдите количество шестизначных чисел, у которых цифра десятков в два раза больше цифры единиц, а сумма цифр сотен и тысяч на 1 меньше суммы цифр десятков тысяч и сотен тысяч. Подсказка: запишите приведённые условия в буквенном виде. В каких границах может изменяться первая цифра шестизначного числа?
