Моё меню Общее меню Сообщество Правила форума Все прочитано
Вернуться   uForum.uz > БЕСЕДКА > Разминка для мозгов
Сообщения за день Поиск
Знаете ли Вы, что ...
...для каждой темы существует свой раздел. Изучите структуру форума. Если соответствующего раздела нет, то всегда есть раздел "Разное" :)
<< Предыдущий совет - Случайный совет - Следующий совет >>

Разминка для мозгов Загадки, задачи, головоломки - тренируем мозг


Ответить

 
Опции темы Опции просмотра
Старый 25.01.2011 18:38   #11  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Shamil Eshbekov Посмотреть сообщение
Коллега изучает Visual basıc. В качестве задачи, поставил решение судоку. Т.е. Хочет написать прогу, которая будет решать судоку любой сложности. Проблема в том, что навыков программирования нет, поэтому подходит к решению проблемы методом тыка. Что ни есть гуд. Умные люди посоветовали ему для начала составить алгоритм решения и набросать блок схему. С чем, в принципе, он согласился. Но опять проблема - не получается это у него. Усилиями коллектива мы тоже не смогли составить правильный алгоритм решения задачи. Какие будут мнения?
DarkUser прав:
Цитата:
Сообщение от DarkUser Посмотреть сообщение
а) Решать полным перебором
Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 25.01.2011 19:37   #12  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,921
+ 3,666  10,931/4,676
– 584  286/214

Uzbekistan
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.
Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки
Ответить 
"+" от:
Старый 25.01.2011 20:11   #13  
Real ID Group uParty Member
Аватар для Shamil Eshbekov
Оффлайн
ITPS-Asia
Инженер АСУТП
AKA:mr.Ses
Сообщений: 1,329
+ 565  493/275
– 53  3/3

UzbekistanМой мир
Цитата:
Сообщение от DarkUser Посмотреть сообщение
ЗЫ Басик - зло в чистом виде
У каждого свои тараканы.
Ответить 
"+" от:
Старый 25.01.2011 20:12   #14  
uParty Member Known ID Group
Аватар для DarkUser
Оффлайн
Служу Его Божественной Тени!
Сообщений: 1,671
+ 4,505  1,372/657
– 164  33/27

Uzbekistan
Цитата:
Сообщение от JH Посмотреть сообщение
Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки
На второй строчке будет уже намного меньше. Плюс уже стоящие цифры, отсеют большое количество вариантов.
__________________
Are you my mommy?
Ответить 
Реклама и уведомления
Старый 25.01.2011 20:17   #15  
Real ID Group uParty Member
Аватар для Shamil Eshbekov
Оффлайн
ITPS-Asia
Инженер АСУТП
AKA:mr.Ses
Сообщений: 1,329
+ 565  493/275
– 53  3/3

UzbekistanМой мир
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.
В том-то и дело, что не получается у него этот полный перебор организовать.
Ответить 
Старый 25.01.2011 20:50   #16  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,921
+ 3,666  10,931/4,676
– 584  286/214

Uzbekistan
Цитата:
Сообщение от DarkUser Посмотреть сообщение
На второй строчке будет уже намного меньше. Плюс уже стоящие цифры, отсеют большое количество вариантов.
Это все так. Но не 729 же...
Ответить 
Старый 25.01.2011 20:57   #17  
Known ID Group uParty Member Ultimate
Аватар для JH
Оффлайн
Сообщений: 10,921
+ 3,666  10,931/4,676
– 584  286/214

Uzbekistan
К автору задачи.
Для начала надо попробовать решить задачу без полного перебора. Пройдемся по всем 81 клеточкам (естественно, незанятым). Для каждой быстренько заводим массив из 9 целых чисел, заполняем его единичками. Потом проходим по всем остальным клеткам квадрата 3х3, в котором находится рассматриваемая клетка, если она не пустая и равна n, то заменяем n-й элемент массива ноликом. Потом то же самое делаем с той строкой, в которой находится текущая клетка, и со столбцом, соответственно. После этой операции суммируем массив, если его сумма равна единице, то вариантов заполнения этой клетки ровно 1, ищем единственный не равный нулю элемент массива и проставляем значение в клетку. Если сумма массива оказалась больше единицы, пропускаем эту клетку. И так проходим по всем 81 клеткам много раз до тех пор, пока алгоритм работает.
После того, как "очевидных" клеток не осталось, придется включать алгоритмы перебора, я в них никогда не был силен.
Ответить 
"+" от:
Старый 26.01.2011 14:48   #18  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от JH Посмотреть сообщение
Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки
Криво посчитал.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 27.01.2011 18:53   #19  
Real ID Group uParty Member Ultimate
Аватар для Nadir Zaitov
Оффлайн
Сообщений: 13,210
+ 4,958  9,176/3,940
– 170  137/105

UzbekistanОтправить сообщение для Nadir Zaitov с помощью Skype™
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Криво посчитал.
Кстати из Википедии
Цитата:
Количество возможных комбинаций в судоку 9×9 составляет, по расчётам Бертхама Фельгенхауэра,
6 670 903 752 021 072 936 960 = (9!)^3
Там нет ссылки на доказательство и, я думаю, доказательство столь интересного факта само по себе интересно.
__________________
Тот факт, что медуза выжила 650 миллионов лет без мозгов, даёт надежду многим.

Последний раз редактировалось Nadir Zaitov; 27.01.2011 в 20:07.
Ответить 
Старый 30.01.2011 15:09   #20  
Real ID Group uParty Member Ultimate
Аватар для Nadir Zaitov
Оффлайн
Сообщений: 13,210
+ 4,958  9,176/3,940
– 170  137/105

UzbekistanОтправить сообщение для Nadir Zaitov с помощью Skype™
Цитата:
Сообщение от JH Посмотреть сообщение
Для начала надо попробовать решить задачу без полного перебора. Пройдемся по всем 81 клеточкам (естественно, незанятым). Для каждой быстренько заводим массив из 9 целых чисел, заполняем его единичками. Потом проходим по всем остальным клеткам квадрата 3х3, в котором находится рассматриваемая клетка, если она не пустая и равна n, то заменяем n-й элемент массива ноликом. Потом то же самое делаем с той строкой, в которой находится текущая клетка, и со столбцом, соответственно. После этой операции суммируем массив, если его сумма равна единице, то вариантов заполнения этой клетки ровно 1, ищем единственный не равный нулю элемент массива и проставляем значение в клетку. Если сумма массива оказалась больше единицы, пропускаем эту клетку. И так проходим по всем 81 клеткам много раз до тех пор, пока алгоритм работает.
Как ни странно, но этот алгоритм при нормальном количестве данных чисел (обычно около 23 на разрешимую таблицу) с вероятностью близкой к 1 ни разу не даст ни одной "очевидной" циферки. Кто-нибудь попробует?
__________________
Тот факт, что медуза выжила 650 миллионов лет без мозгов, даёт надежду многим.
Ответить 
Ответить




Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd. Перевод: zCarot
Advertisement System V2.5 By Branden
OOO «Единый интегратор UZINFOCOM»


Новые 24 часа Кто на форуме Новички Поиск Кабинет Все прочитано Вверх