Премини към съдържанието
ChrisJobs

Някакви идеи как се решава задачата?

Препоръчан отговор


Бикове и Крави

Вместо да учат по програмиране, Сотир и Гьозума играят на Бикове и Крави вече 7 часа.

Тази игра се играе от двама участници. В началото на играта всеки от тях намисля по едно 4 цифрено число. По време на играта участниците се опитват да отгатнат числото на противника, като правят предположения. След всяко предположение противника отговаря колко точни съвпадения на цифри има между неговото число и предположението на противника (бикове) и колко цифри от предположението присъстват в числото му, но не са на правилните си места (крави). Играта продължава докато някой от двамата не познае числото на противника.

Помогнете на Сотир и Гьозума да спрат да играят, като напишете програма, която играе вместо тях.

На стандартния вход програмата печата намисленото число. До достигане на условието за прекратяване на изпълнението, програмата печата на стандартния изход следващото си предположение и след това прочита от стандартния вход резултата от противника във формат "n,k", където n е броят бикове, а k е броят крави. Изпълнението на програмата продължава докато от стандартния вход не бъде прочетен низа '4,0'.

Пример срещу противник с число 4321:

 

Вход: Изход:

0,4 1234

2,2 1234

2,2 4231

4,0 4312

  4321

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

За такива стандартни задачи Google помага много: цък

  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)

Интересно ... 

 

Наскоро с един колега на работа се занимавахме именно да оптимизираме алгоритъм за бикове и крави при който компютъра да познава числото до максимум 6-тия ход. Линка, който колегата maxim4o е дал ще е полезен за проверките, който ще са Ви необходими, за да определите биковете и кравите, но не и методиката по която компютъра да определя предложението. Мога да Ви дам няколко насоки по отношение на задачата, защото има няколко съществени момента, които са изпуснати от условието (надявам се не умишлено)

 

//По отношение на точка 1), моля прочете коментар №4 в зависимост от варианта на играта !

1) Когато говорим за четирицифрени числа за игра "Бикове и Крави", в общия случай говорим за числа, чиито цифри са неповтарящи се в записа И числото не започва с 0-ла. Т.е. числа от вида 2235 или 5555 са недопустими. Защо ? Как биха се определили кравите и биковете на подобно число ? Ако имате 5555 и предложите 5534 и 3552 какво имате ? Два бика ? Две крави ? Или 2 бика и 2 крави ? Поради това, трябва предложението да се валидира - не да е само през random-а.

 

2) Трябва да се помисли и за "история" на предложенията - какво е предложено досега ... Ако ще се ползва random генерирано предложение, не искаме да питаме по N пъти за едно и също, при положение, че вече знаем, че не е отговор.

 

3) Трябва по някакъв начин да се запазва отговора на потребителя - т.е. за дадено число при даден отговор от X бикове и Y крави, това да се използва при следващото предлагане. Иначе можем спокойно да си изпаднем в случая да питаме за всички възможни числа (9*9*8*7 = 4536 са на брой :) ). Аз лично не бих имал нерви да въвеждам 2000+ пъти отговор на въпроси, който в повечето случаи ще са нещо, което няма нищо общо с намисленото  :).

 

Ще Ви дам hint откъде можете да започнете - предварително изгенерирайте всички комбинации и ги пазете в едно множество. След това вземате едно число от това множество и го предложете. Получавате отговор и от това множество, махате всички които НЕ СЕ подчиняват на отговора, който сте получил. Горното се прилага до момента в който или на входа не получим 4,0 или имаме само едно предложение, останало в множеството.

 

ПРИМЕР:

Предлагате числото 1234 и получавате 0 бикове и 0 крави. Това означава, че числото, което е отговора няма нито една от цифрите в записа си. По този начин можете от множеството с предположения да премахнете всички числа, в чиито запис има която и да е цифра от записа на 1234 (Не забравяме да махнем и 1234 все пак :) ).

 

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

Hint-а може да се доразвие и с малко AI, като се приложи Бейсов класификатор за избор на предложението, според вероятността дадена цифра на дадена позиция да бъде в отговора. Това е просто като идея, защото реалната му реализация изисква и някакви познания в AI алгоритмите и статистиката. Това може да се направи едва след като основния алгоритъм вече работи и търсим оптимизации. 

 

Надявам се това да Ви помогне и да Ви насочи в решаването на задачата. 

 

Поздрави !

Редактирано от soundtracker (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

1) Когато говорим за четирицифрени числа за игра "Бикове и Крави", в общия случай говорим за числа, чиито цифри са неповтарящи се в записа И числото не започва с 0-ла. Т.е. числа от вида 2235 или 5555 са недопустими. Защо ? Как биха се определили кравите и биковете на подобно число ? Ако имате 5555 и предложите 5534 и 3552 какво имате ? Два бика ? Две крави ? Или 2 бика и 2 крави ? Поради това, трябва предложението да се валидира - не да е само през random-а.

Логиката ти се отхвърля. Ние сме играли едно време на листчета с точно такива правила. Не виждам, какво пречи първото число да е нула (приеми я за символ, каквото значение именно се ползва в играта а не за "незначещата цифра"). Относно повтарянето, биковете се броят с предимство и всяка цифра се брои само по веднъж. Така играта става доста по-сложна и по-интереснаДа не опираме до бикове и крави с hex или повече от 4 цифри :PИначе останалото е доста отработено.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Логиката ти се отхвърля. Ние сме играли едно време на листчета с точно такива правила. Не виждам, какво пречи първото число да е нула (приеми я за символ, каквото значение именно се ползва в играта а не за "незначещата цифра"). Относно повтарянето, биковете се броят с предимство и всяка цифра се брои само по веднъж. Така играта става доста по-сложна и по-интереснаДа не опираме до бикове и крави с hex или повече от 4 цифри :PИначе останалото е доста отработено.

Правилата на играта са да не започва с нула. Иначе имах преди години (82-83 година) една програмка на PL/1 която се справяше на прилично ниво :)


Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Логиката ти се отхвърля. Ние сме играли едно време на листчета с точно такива правила. Не виждам, какво пречи първото число да е нула (приеми я за символ, каквото значение именно се ползва в играта а не за "незначещата цифра"). Относно повтарянето, биковете се броят с предимство и всяка цифра се брои само по веднъж. Така играта става доста по-сложна и по-интереснаДа не опираме до бикове и крави с hex или повече от 4 цифри :PИначе останалото е доста отработено.

Явно във варианта в който аз я знам са я "оптимизирали" :P

Щом биковете са с предимство, това може да си се изпрограмира без драми. С HEX или повече от 4 цифри нещата мисля, че стоят аналогично :). Е, няма да са 4536 възможности със сигурност, но принципите би трябвало да останат.

 

Поздрави !

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Правилата на играта са да не започва с нула. Иначе имах преди години (82-83 година) една програмка на PL/1 която се справяше на прилично ниво :)

Ми незнам. Ние сме я играли с и без повтарящи се числа, но винаги с 0. Както казах, в тази игра цифрите и числата нямат значение на такива. Няма да има никаква разлика, ако ги замениш с буквите от a до j, нали? И тогава няма ли да е странно правило, че 'а' не може да е първа?П.П. Сметката за средния брой познавания в страницата в уикипедията е с 0 на първо място включително.
  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

На практика няма голяма разлика, 5040 числа ако може да почва с нула и 4536 - ако не може - сигурно не увеличава с повече от един необходимите ходове да се познае числото

  • Харесва ми 3

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

На практика няма голяма разлика, 5040 числа ако може да почва с нула и 4536 - ако не може - сигурно не увеличава с повече от един необходимите ходове да се познае числото

Въпросът е религиозен. :) Изключително съм против необосновани изключения, като това тука. Заради такива неща, в проклетите самолети няма седалки 13и номер :D
  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Ми незнам. Ние сме я играли с и без повтарящи се числа, но винаги с 0. Както казах, в тази игра цифрите и числата нямат значение на такива. Няма да има никаква разлика, ако ги замениш с буквите от a до j, нали? И тогава няма ли да е странно правило, че 'а' не може да е първа?П.П. Сметката за средния брой познавания в страницата в уикипедията е с 0 на първо място включително.

Исторически е без нула защото тази нула би била незначеща.Освен това без повтарящи се числа се намалява броя комбинации :)

 

На практика няма голяма разлика, 5040 числа ако може да почва с нула и 4536 - ако не може - сигурно не увеличава с повече от един необходимите ходове да се познае числото

Всъщност намалява броя на ходовете с около 1/3 ход :) Което понякога може да е разликата между победа и загуба. Освен това личните ми наблюдения показват че на човек му е по-лесно да се ориентира и да реши задачата (наум или само с лист хартия) ако няма повтарящи се

Въпросът е религиозен. :) Изключително съм против необосновани изключения, като това тука. Заради такива неща, в проклетите самолети няма седалки 13и номер :D

както и Канон нямат G4 и G8 (4 и 8 са "нещастни" числа за японците)

  • Харесва ми 3

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)

Ми незнам. Ние сме я играли с и без повтарящи се числа, но винаги с 0. Както казах, в тази игра цифрите и числата нямат значение на такива. Няма да има никаква разлика, ако ги замениш с буквите от a до j, нали? И тогава няма ли да е странно правило, че 'а' не може да е първа?П.П. Сметката за средния брой познавания в страницата в уикипедията е с 0 на първо място включително.

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

 

P.S. Мисля, че мнението на @flare по отношение на правилата би дало реализацията на такъв алгоритъм, който да покрие и трите версии. 

@ined : Почти съм сигурен, че в голям процент от случаите, броя въпроси ще остане непроменен, защото няма да се прави нищо по - различно от това, което е правено досега като логиката. Ако настъпи допълнително запитване, то ще е в много редки случаи ...

 

Поздрави !

Редактирано от soundtracker (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

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

 

P.S. Мисля, че мнението на @flare по отношение на правилата би дало реализацията на такъв алгоритъм, който да покрие и трите версии. 

@ined : Почти съм сигурен, че в голям процент от случаите, броя въпроси ще остане непроменен, защото няма да се прави нищо по - различно от това, което е правено досега като логиката. Ако настъпи допълнително запитване, то ще е в много редки случаи ...

 

Поздрави !

Аз лично си мисля че ако не започват с нула и няма повтарящи се алгоритъма за познаване може да се опрости и ускори :)

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Аз лично си мисля че ако не започват с нула и няма повтарящи се алгоритъма за познаване може да се опрости и ускори :)

Оооо, определено !

С колегата, само с математически операции, сведохме познаването на числото до 5-тия път и мнооого рядко идваше 6-ти въпрос. И то само в случаите, когато предните предложения бяха относително слаби, или отговорите не махаха достатъчно на брой възможности от множеството. В случая, при тестване, видяхме, че алгоритъма се държеше малко в стил Hill Climbing - т.е. на всеки въпрос, в отговора се появяваше или нова крава, или крава ставаше бик или и двете.

 

Мисля си, че дори и да има повтарящи или да има започваща 0-ла, това не би дало твърде голямо отражение.

Всичко обаче ще опре до това "ситото" на числата много добре да обработва потенциално повтарящи се цифри, които ще дойдат като бикове и/или като крави. 

 

Поздрави !

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.