Итоги первого задания
Автор Виталий   
20.07.2002 г.
Ну, вот и пришло время подвести некоторые итоги по первому туру конкурса.
Ну, вот и пришло время подвести некоторые итоги по первому туру конкурса. Как заметили участники, вопросы первого тура не отличались занудностью. Я специально старался выбрать вопросы поинтересней, приближенные к жизни. Ну какие обычно задачи на олимпиадах по программированию: " Найти сумму элементов А(i,j) массива A(1:m,1:n), имеющих заданную разность индексов i - j = k, где k может быть отрицательным ". Возможно, это и интересно, но как то занудно. Вместе с тем, решения некоторых заданий не так просты, как кажется. Сегодня хочется остановиться на первом задании:
1.1 Покер
Эта задача (как и все остальные) имеет столько решений, сколько было участников. Отметая тех, кто явно не понял задания, ( к примеру "Rus Kend" - прога выдавала среднее арифметическое, кол-во совпадений чисел, но только не то, что надо по заданию) решали в основном так: На примере Дмитрия Данелия суть алгоритма такова: вначале ищется пара далее ищется третья карта, совпадающая с этой парой если третьей нет - проверяются три оставшиеся, если есть третья - ищется четвертая если нет четвертой - проверяются две оставшиеся, если есть четвертая - сразу проверяется и пятая. Некоторые применяли сортировку списка как Иван aka Atlanoff, а потом в отсортированном списке искали совпадения.
Финал кода - обычно конструкция Select case или If ..Then. Есть и оригинальные решения. Понравилось работа Дмитрия Бирюкова, его алгоритм основан на анализе количества ошибок вставки в коллекцию всех элементов и на количестве ошибок вставки повторяющихся элементов. Вот только жалко, что не соблюдены условия задания - в массиве должны быть числа, а не цифры. Ведь покер - ира в карты, а колоду из 52 карт не представить 10 цифрами...
Очень понравилось решение Павлова Александра, оно очень близко подходит к наиболее рациональному решению этой задачи. Суть такова :сравниваем значение каждой переменной массива с самой собой и со всеми остальными переменными массива и если их значения равны, то увеличиваем счетчик совпадений на единицу. Но он усложнил расчет конечного результата, сравнивая переменную с самой собой (зачем?) Действительно, для этой задачи имеется очень простое решение. Надо сосчитать сколько равных пар имеется в данном массиве чисел. Число этих пар ОДНОЗНАЧНО характеризует любую комбинацию. Т.е. каждый элемент массива сравнивается со всеми последующими, и в случае равенства, к счетчику совпадений прибавляется единица.
Что и было блестяще использовано в программе Склярова Романа. Вот ее текст:
Private Sub Cmd_Click()
Dim Num(5) As Integer 'Задаем массив из 5 чисел
Dim Ident As Integer 'Количество одинаковых чисел
Cls 'Очистка формы
For I = 1 To 5
Randomize Timer
'Записываем в массив случайные числа от 1 до 5
Num(I) = Int(Rnd * 5) + 1
'Вывод чисел на форму
Print Num(I);
Next
For I = 1 To 5
For J = I To 5
If I <> J Then
If Num(J) = Num(I) Then
'Если найдены одинаковые числа,
' то пополняем массив одинаковых
Ident = Ident + 1
End If
End If
Next
Next
Select Case Ident
Case 1
'Пара одинаковых
Number = 6
Case 2
'Две пары
Number = 5
Case 3
'Тройка одинаковых
Number = 4
Case 4
'Двойка и тройка
Number = 3
Case 6
'Четверка одинаковых
Number = 2
Case 10
'Пять одинаковых
Number = 1
Case Else
'Одинаковых нет
Number = 7
End Select
MsgBox Number

Отличное решение, но не идеальное. Роман не увидел одну закономерность, которая позволит существенно уменьшить код программы. Кроме двух последних случаев Ident=10 и Ident=6 результат
Number = 7 - Ident. Т.е. можно исключить конструкцию Select Case Ident, записав
If Ident = 6 Then Ident = 5
If Ident = 10 Then Ident = 6
MsgBox 7 - Ident
Т.о. сократив код на 14 строк!
Вот что получится:
Private Sub Cmd_Click()
Dim Num(5) As Integer 'Задаем массив из 5 чисел
Dim Ident As Integer 'Количество одинаковых чисел
Cls 'Очистка формы
For I = 1 To 5
Randomize Timer
Num(I) = Int(Rnd * 5) + 1
Print Num(I);
Next
For I = 1 To 5
For J = I To 5
If I <> J Then
If Num(J) = Num(I) Then
Ident = Ident + 1
End If
End If
Next
Next
If Ident = 6 Then Ident = 5
If Ident = 10 Then Ident = 6
MsgBox 7 - Ident
End Sub
А вот вариант программы, из ответов на задачу :
(Опущены явные обвления переменных, что не суть важно)
Private Sub Command1_Click()
Dim A(5)
Randomize Timer
Cls
For i = 1 To 5
A(i) = Int(Rnd * 10)
Print A(i)
Next i
s = 0
For i = 1 To 4
For j = i + 1 To 5
If A(i) = A(j) Then s = s + 1' счетчик совпадений
Next j
Next i
If s = 6 Then s = 5
If s = 10 Then s = 6
Print 7 - s
End Sub
Ну, кто сможет написать короче? Можно спорить по известному адресу конкурса. На сегодня все. Ответы на это задание можно присылать, но если они как то радикально изменят её решение. Все решения упамянуть просто невозможно, но у всех есть шанс ! Обзор остальных задач в последующих выпусках.


Виталий.