Каждому учителю информатики приходится сталкиваться с необходимостью подготовки учеников к олимпиадам. И так как программирование является достаточно специфичной областью информатики, не всякий учитель увлекается им. На помощь могут прийти задачи повышенной сложности с готовыми решениями. И чем их больше у учителя, тем лучше. Совместный анализ решения задач дает возможность понять приемы решения подобных задач. Очень часто прием, примененный в одной задаче, приводит к решению другой задачи. Порой над решением задачи мы с учениками трудимся не одну неделю. Решение находится достаточно быстро, а его совершенствование превращается в соревнование на более красивый алгоритм. В данной статье это видно на примере решения задачи “Самое длинное слово”. Решения приведены на наиболее простом и распространенном языке программирования QBasic.
“Крестики-нолики”
Правила игры классические. Игра в крестики-нолики ведется на квадратном поле 3х3. Играют двое. Начинают “крестики”. Каждый из игроков, поочередно, ставит свой значок, крестик или нолик, на свободную клетку. Выигрывает тот, кто первым поставит три своих значка в ряд по вертикали, горизонтали или диагонали. Задается последовательность ходов. Определить, кто выиграл, “крестики” или “нолики”? Последовательность ходов задается 9-значным числом. Цифра числа обозначает номер клетки хода, а порядковый номер цифры – номер хода. Клетки пронумерованы так, как показано на рисунке. Написать программу, которая запрашивает код позиции и выводит значок выигравшей стороны или слово “ничья”.
Пример. Вход: 123456789. Выход: х.
Примечание. В примере приведена позиция, показанная на втором рисунке. Очевидно, что последние два хода лишние, но они нужны для девятизначности кода позиции.
Основные сложности при решении задачи возникают при проверке правильности вводимого кода и проверке, кто победил. И в том и другом случае применяем метод контрольных сумм.
'крестики-нолики
CLS
DIM a(3, 3)
1 INPUT "Введите последовательность ходов ", h$
'проверка на корректность ввода
IF LEN(h$) <> 9 THEN GOTO 1
s = 0
FOR i = 1 TO 9
e = 1
FOR j = 1 TO 9
IF i = VAL(MID$(h$, j, 1)) THEN
s = s + e: e = 10
ELSE
END IF
NEXT j
NEXT i
IF NOT (s = 9) THEN GOTO 1 ELSE
'решение задачи
k = -1 'чей ход "1" - крестики, "-1" - нолики
s1 = 0: s2 = 0: s3 = 0: s4 = 0: s5 = 0: s6 = 0: s7 = 0: s8 = 0: flag = 0
FOR i = 1 TO 9
k = (-1) * k
SELECT CASE VAL(MID$(h$, i, 1)) 'проверяем всевозможные комбинации
CASE 1: a(3, 1) = k: s8 = s8 + k: s3 = s3 + k: s2 = s2 + k
CASE 2: a(3, 2) = k: s8 = s8 + k: s4 = s4 + k
CASE 3: a(3, 3) = k: s8 = s8 + k: s5 = s5 + k: s1 = s1 + k
CASE 4: a(2, 1) = k: s7 = s7 + k: s3 = s3 + k
CASE 5: a(2, 2) = k: s7 = s7 + k: s4 = s4 + k: s2 = s2 + k: s1 = s1 + k
CASE 6: a(2, 3) = k: s7 = s7 + k: s5 = s5 + k
CASE 7: a(1, 1) = k: s6 = s6 + k: s3 = s3 + k: s1 = s1 + k
CASE 8: a(1, 2) = k: s6 = s6 + k: s4 = s4 + k
CASE 9: a(1, 3) = k: s6 = s6 + k: s5 = s5 + k: s2 = s2 + k
END SELECT
IF flag = 0 THEN
IF (ABS(s1) = 3) OR (ABS(s2) = 3) OR (ABS(s3) = 3) OR (ABS(s4) = 3) OR (ABS(s5) = 3) OR (ABS(s6) = 3) OR (ABS(s7) = 3) OR (ABS(s8) = 3) THEN
IF k = 1 THEN
t$ = "на " + STR$(i) + "-м ходу победили х": flag = 1
ELSE
t$ = "на " + STR$(i) + "-м ходу победили 0": flag = 1
END IF
ELSE
END IF
ELSE
END IF
NEXT i
IF flag = 0 THEN t$ = "ничья"
PRINT t$
'Вывод окончательной позиции
FOR i = 1 TO 3
FOR j = 1 TO 3
IF a(i, j) = 0 THEN
PRINT " ";
ELSE
IF a(i, j) = 1 THEN PRINT " x "; ELSE PRINT " o ";
END IF
NEXT j
NEXT i
“Заготовка”
Можно ли из прямоугольной заготовки размером a x b вырезать две прямоугольные пластины размером c х d и k x m ? Даны шесть натуральных чисел (величина чисел от 1 до 200), если две пластины вырезать удается, то вывести слово “Да”, иначе – слово “Нет”.
Технические требования: Все числа вводятся с клавиатуры в следующем порядке: a, b, c, d, k, m. Ответ вывести на экран.
Пример. Для a=6, b=3, c=1, d=3, k=7, m=1 ответом будет “Нет”.
Задача достаточно простая. Но у школьников трудности возникают с всевозможным перебором вариантов проверки.
CLS
PRINT "Введите значения заготовок"
INPUT a, b, c, d, k, m
IF (a >= (c + k)) AND (b >= d) AND (b >= m) THEN
PRINT "да"
ELSE
IF (a >= (c + m)) AND (b >= d) AND (b >= k) THEN
PRINT "да"
ELSE
IF (a >= (d + m)) AND (b >= c) AND (b >= k) THEN
PRINT "да"
ELSE
IF (a >= (d + k)) AND (b >= c) AND (b >= m) THEN
PRINT "да"
ELSE
IF (b >= (c + k)) AND (a >= d) AND (a >= m) THEN
PRINT "да"
ELSE
IF (b >= (c + m)) AND (a >= d) AND (a >= k) THEN
PRINT "да"
ELSE
IF (b >= (d + m)) AND (a >= c) AND (a >= k) THEN
PRINT "да"
ELSE
IF (b >= (d + k)) AND (a >= c) AND (a >= m) THEN
PRINT "да"
ELSE
PRINT "нет"
END IF
END IF
END IF
END IF
END IF
END IF
END IF
END IF
“Простые делители”
Дано натуральное число N (2<N<1000000). Получить все простые делители этого числа меньшие N. Примечание: число называется простым, если оно не имеет делителей кроме единицы и самого себя.
Технические требования: число N вводится с клавиатуры. Ответ вывести на экран.
Пример. Для N=75 ответом будет 1,3,5.
Для убыстрения работы программы в массиве А копятся простые числа.
CLS
1 INPUT "Введите число N (2<N<1000000)"; n
IF (n <= 2) OR (n >= 1000000) THEN CLS : GOTO 1 ELSE
DIM a%(1000)
a%(1) = 2: a%(2) = 3: k = 2
PRINT 1;
IF (n MOD 2 = 0) AND (n <> 2) THEN PRINT 2;
IF (n MOD 3 = 0) AND (n <> 3) THEN PRINT 3;
m = 3
WHILE m < SQR(n)
m = m + 2
IF n MOD m = 0 THEN
flag = 0
FOR i = 1 TO k
IF m MOD a%(i) = 0 THEN flag = 1
NEXT
IF flag = 0 THEN k = k + 1: a%(k) = m: PRINT m;
END IF
WEND
“Самое длинное слово”
В строке S записано несколько слов, разделенных пробелами (длина строки менее 200 символов). Найдите самое длинное слово, выведите его на экран, а так же его длину.
Технические требования: Строка S вводится с клавиатуры, решение выводится на экран.
Пример: Для S= “мышь клавиатура монитор дисковод колонки” ответом будет “клавиатура” 10.
Решение задачи с использованием массивов. Работаем со словами.
PRINT "Введите строку"
INPUT a$
a$ = a$ + " "
n = 0'Количество пробелов т.е слов
FOR i = 1 TO LEN(a$)
IF MID$(a$, i, 1) = " " THEN n = n + 1
NEXT i
DIM D$(n) 'Резервируем места под слова
'Режем на слова
k = 1: b$ = ""
FOR i = 1 TO LEN(a$)
c$ = MID$(a$, i, 1)
IF c$ <> " " THEN b$ = b$ + c$ ELSE D$(k) = b$: b$ = "": k = k + 1
NEXT i
'Ищем самое длинное
m = LEN(D$(1)): t = 1
FOR i = 2 TO n
IF m < LEN(D$(i)) THEN m = LEN(D$(i)): t = i ELSE
NEXT i
'Выводим результат
PRINT D$(t), m
Просто решение без массива. Работаем со словами как с числами.
PRINT "Введите строку"
INPUT a$
a$ = a$ + " "
'Режем на слова Ищем самое длинное
k = 0: b$ = "": m$ = ""
FOR i = 1 TO LEN(a$)
c$ = MID$(a$, i, 1)
IF c$ <> " " THEN
b$ = b$ + c$
ELSE
IF LEN(m$) < LEN(b$) THEN m$ = b$: k = LEN(b$): b$ = "" ELSE
END IF
NEXT i
'Выводим результат
PRINT m$, k
Еще одно решение с использованием массивов. Работаем с числами.
CLS
INPUT "Введите строку"; a$
a$ = a$ + " "
n = LEN(a$)
DIM a(n)
k = 0
FOR i = 1 TO n
IF MID$(a$, i, 1) = " " THEN k = k + 1: a(k) = i ELSE
NEXT
m = a(1) - 1: x = 1: y = a(1)
FOR i = 2 TO k
m1 = a(i) - a(i - 1)
IF m < m1 THEN m = m1: x = a(i - 1): y = a(i) ELSE
NEXT
PRINT MID$(a$, x, m)