практическая задача

[TopIce]

Была у меня на старом сотовом занимательная игра, в ней предлогалось отгадать задуманое ею шестизначное число с наименьшего количества попыток, на каждую попытку программа выдавала подсказку в виде:
х-чисел верны и находятся на своих местах
у-чисел верны, но не на своем месте

на примере:
Пусть загадано число 9245, а угадывающий делает ход 1294. Тогда ему приходит следующий ответ от загадавшего: 1х (совпали вторые цифры по позиции) + 2у (так как в обоих числах есть четвёрки и девятки, но они на разных позициях).

Задача:
Придумать алгоритм программы которая будет разгадывать число загаданое человеком с минимальным количеством попыток

[Ольга_13]

Вроде бы есть такие программы типа : разделить на ... , вычесть ... , потом умножать....
А вообще врятли какая либо программа может угадать цисло находящееся в мыслях. Это скорее экстрасенс, и то они этим не занимаются... мыслей в голове много и 1 цифорку найти....
Хотя если придумать аппарат, одеваемый на голову... и проводимым током в определенную часть головы он мог бы выводить хотя бы что нибудь похожее на цифру.... было бы весело...

[Balrog]

Чет ты не про то кажется. Прочитав твой пост, вспомнил серию Хауса, где пациент лишившийся вообще любой возможности контактировать с миром, даже глазами пошевелить не мог, мысленно с помощю какого то устройства дывигал стрелку на экране вверх и вниз. Он слышал. и движением отвечас на вопросы, подразумевающие ответ да или нет.

[TopIce]

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

[KIZ]

Число представляем в виде массивчега из 6 элементов.(a) Ещё один булевский такой же размерности - это будет вектор совпавших цифр(на своих местах стоят уже, ни в одном из пунктов их не учитываем).(b) Ещё треба матрицу 6 на 10, для запоминания уже проверенных и не совпавших чисел на каждой позиции(при случайном бросании на это место их уже не учитываем).(c)

1.Очередная попытка - случайная.(Здесь и далее уже совпавшие цифры не трогаем.)

2.После каждой попытки анализ:
Если число совпавших чисел с предыдущей попытки не увеличилось(ни x ни y) - ещё раз случайно за вычетом уже совпавших и уже попробованных цифр.

3.Если увеличилось число совпавших(x): последовательно меняем на любую другую цифру элементы массива а, добиваемся того, чтобы выдаваемое число x уменьшилось на 1. Таким образом вычисляем совпавшую цифру, отмечаем в массиве b соответствующий элемент. Если совпало больше двух - повторяем.(Есть простор оптимизации, если к примеру в процессе отыскания x или y увеличился, неплохо бы с этим числом в начало пункта идти).

4.Если увеличилось y: Последовательно берём каждую цифру и меняем её местами с другими. Ждём пока x не увеличится, а y не уменьшится(на 1 или 2).Важно, чтобы x увеличился на столько же, насколько y уменьшился, только тогда можно иметь гарантию что совпали нужные числа. Если x увеличился только на 1, тогда ещё надо выяснить, какое из двух обменянных чисел совпало. (Ясен пень, что только первое число меняем со всеми остальными, второе уже с первым не меняем, третье с первыми двумя и т.д.)

5.Усё, запоминаем новые текущие x и y и идём пытать щастье дальше на пункт 1.

[TopIce]

перебор в пол дня. можно делать это в меньшее количество ходов(попыток).

[KIZ]

Даже самый старенький микропроцессор сделает это максимум за несколько секунд, ибо постоянно вычёркиваются совпавшие + уже опробованные. Есесено ИМХО, не отрицаю существование более быстрого алгоритма.

[TopIce]

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

[kudessnik]

форум упоротых программистов?

[KIZ]

Упростил немного, хотя быстрее или медленнее стал работать - ?

На каждом шаге случайно бросаем одну цифру, один разряд только меняем. За вычетом тех разрядов, кот уже пофиксили.

Если уменьшилось x или y - делаем откат на предыдущее число. Фиксируем этот разряд, как уже совпавший, больше его не трогаем.

Не изменилось - ещё раз случайно бросаем тот же разряд.

Увеличилось - запоминаем новое число, фиксим этот разряд как совпавший.

Делаем так, пока x + y < 6.

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

(Ради простоты выкинул из процесса случайного бросания момент учитывания уже попробованных на этот разряд цифр. Лучше конечно его вставить, будет гарантия сходимости.)