Проблемът с изчисляването на броя на късметлийските билети е известен отдавна. Беше зададен от почти всеки студент, изучаващ програмиране. В интернет можете да намерите много от неговите решения различни езиципрограмиране. Всички тези опции се свеждат до сортиране на всички съществуващи билети и проверката им за „щастие“. Има милион варианти.
Но тази задачамогат да бъдат решени по друг начин, преминавайки само през хиляди варианти.
Напомням, че билетите са късметлии, сборът на първия три цифричиито числа са равни на сбора последните трицифри на числото. Например номерът на билета "546780" е щастлив, защото сборът от първите три цифри (5+4+6) е равен на сбора от последните три цифри (7+8+0). Проблемът е да се определи колко късметлийски билета има.
Във всички примери се решава челно, но какво ще стане, ако тръгнем по обратния път? Нека първо отговорим на друг въпрос. Колко различни комбинации от три цифри (тройки) има, които се събират до н? За да отговорите на този въпрос, трябва да преминете през всички възможни тройки (хиляда варианта).
Сборът на всички тройки е между нула (0+0+0) и 27 (9+9+9). Следователно можете да подготвите масив от суми:
{n_0, n_1, n_2, n_3, …., n_25, n_26, n_27}
където н _ аз- броят на тройките, които се събират аз. В този случай сумата от цифрите е равна на индекса на този елемент в масива.
Добре, ще подготвим такъв масив, но какво общо има това с билетите? Нека разгледаме частен случай. Общо съществува n_25тройки, които се събират до 25. За всяка такава тройка съществува n_25тройки, когато се комбинира с всяка от които ще доведе до щастливо число. Следователно има n_25*n_25късметлийски билети, чийто сбор от първите три цифри е 25. Аналогично и за останалите суми. Така общият брой късметлийски билети е равен на:
n_0*n_0 + n_1*n_1 + …. + n_26*n_26 + n_27*n_27
По-долу е пълният изходен код на приложението, което изпълнява този алгоритъм.
#включи
Кодът е добре коментиран, така че не трябва да възникват въпроси.
Разглеждайки масива от суми, можем да направим две наблюдения.
1. Той е симетричен:
n_13 = n_14,
n_12 = n_15,
n_11 = n_16,
n_10 = n_17,
………………
n_1 = n_26,
n_0 = n_27.
2. Най-много има билети, чийто сбор от първите три цифри е 13 и 14 (те са 75).
Масив от суми от 28 елемента се подготвя в едно преминаване на тройки. Следователно, за да изчислите броя на късметлийските билети, е достатъчно да сортирате 1000 опции.
Повечето ученици знаят добре какво е „късметлийският билет“. Да, и учениците често също. Вярно, какви точно са те и какво да правим с тях - тук мненията най-често се различават.
Преди всичко, "ученик щастлив"се счита билет, чиито отговори знаете. Дори не ходете при баба си тук - имахте късмет на изпита, извадихте късметлийски билет и го издържахте от първия път, въпреки че от сто въпроса само тези двамата успяха да научат. Да, отговори толкова живо, че учителят, уморен от „бе-кане и ме-кане“, дори не те изслуша докрай – изпрати те с петица в учетната книжка и с указания към останалите: "Ето! Гледайте и се научете как да минавате темата! Вземете пример от този добър човек!"
Това разбирам - "щастлив билет"!
Но има билети, те са и купони за пътуване, които се смятат или за щастливи, или за красиви. Второто е изключително рядко. Най-често те се наричат именно "щастливи"! Какъв вид билети се считат за такива?
Първо, и това е изключително рядък случай, за късмет се счита билет, чиито цифри са еднакви или симетрични.
Например: 555555
или 252252
. Има пълна симетрия.
Но понякога симетрията е непълна или огледална. Например така: 251251
- числата тук са подредени симетрично, но числата не са.
Във всеки случай, горните примери са наистина "щастлив"билети. Има ли много от тях? Е, мисля, че можете лесно да изчислите това много, много малко - хиляда на милион или всеки хиляден билет. Вероятността такъв билет да попадне в ръцете на пътник е изключително малка. Досега съм получил само два такива билета в живота си, въпреки че пътувам с градския транспорт доста често,
Искаш ли щастие? Ето защо хитрите и бързи пътници в скуката на пътя веднага измислиха други възможности за "щастие". Например, просто същите цифрив стаята, подредени в произволен ред: 251521
, например. Тук няма симетрия, но всички числа присъстват. Освен това. Билет се смяташе за късметлия, чиято сума от тройките цифри е еднаква. Например, 474195:
4+7+4=15= 1+9+5
1. Примери за билети, "щастлив като цяло":
Отново всеки знае, че такива билети се намират, макар и не всеки ден, но все пак доста често. Приблизително всеки 18-ти билет е „щастлив по отношение на сумата“. И ако пътувате постоянно, тогава те се срещат поне веднъж седмично. По някакъв начин проведох малък експеримент: не го изхвърлих, а сложих тези билети в джоба на чантата си, за да ги преброя в края на месеца. Беше много отдавна, не помня точно колко, но за един месец имах поне десет от тях. Като се има предвид, че пътувам с общински транспорт средно два-три пъти на ден (останалото време са маршрутки и по някаква причина там не е обичайно да се издават билети), се оказва, че всеки 6-9 пътувания е "награден "с такова просто щастие. Е, или един билет за три дни. Но това, разбирате ли, имам добър месец, защото всеки 18-ти билет трябва да се среща сякаш по-рядко.
Наистина, има моменти, когато за един месец не е хванат нито един. И така, какво да правя? А нуждата от изобретения е хитра. Например има билети "щастлив в Москва"(те са - "в Ленинград") е когато се броят не тройки числа, а техните двойки. Например сумата на всеки четен бройс коефициент: 6 3
49
86
.
Тук:
3+9+6= 18= 6+4+8
Какво мислите, възможно ли е, освен допълнение, да се приложи операцията изваждане? Разбира се можете да! Основното е да решите сами как да изваждате - по ред или от по-голямо към по-малко: 720821 . Тук:
7-2-0=5= 8-2-1
Но ... не е обичайно да "изваждаме щастието" по някакъв начин. По-добре е, когато се добавя или дори умножава!
Така че измислих друг вид късметлийски билети за себе си: "късмет с умножение"!
Достатъчно е да умножите числата по тройки, за да получите допълнително "множител"бодрост. Например: 338924.
Тук:
3*3*8=72= 9*2*4
Използвайте със здраве! Но защо обобщавате всичко и го обобщавате ... Можете също така да умножавате!
Upd: Освен това не можете просто да умножавате! Тук в коментарите docbrowns Забелязах, че можете също да повдигнете на степен! Например 261812 :
(2^6)^1 = 64 = (8^1)^2
И това все още многократно увеличава както шансовете за „намиране на щастието“, така и забавлението от пътуването.
2. Пример за билет, "късмет с умножение"а ла: 
Ако използвате обществен транспортпогледнете по-отблизо пътниците. Много, много често можете да видите как, когато получат билет, те започват да изучават номерата му. Всеки търси щастието ... И тогава какво да прави с него? Веднъж чух разговор между две момичета, които отиваха на теста: "Уау! Имам билетче на късмет!" — възкликна единият. "Изяж го! Тогава ще издържиш теста!!!" - веднага отговори вторият. Добре, засмях се. По-добре се надяваха на това щастливи "студент"билета, който споменах в началото. И още по-добре - така че всичките петдесет билета за курсове да са щастливи за тях. Но...предпочитат да ядат тролей, отколкото да преподават лекции.
Момчета! Няма нужда да ядете купони! Дори не е никак полезно. И това няма да ви донесе щастие. лечение късметлийски билетипо-лесно - пъти той си падна по теб, тогава щастието няма да дойде, не - вие вече щастливили по-просто, късметлиячовек! Това е всичко. Това е само извинение, за да подобрите леко настроението си. Не вярвайте на знаците - те далеч не винаги се основават на факти и често могат да навредят, особено ако започнете да ядете четирилистни цветя от земята или рециклирани хартиени купони в автобуса! Като в онзи виц: изяде късметлийски билет и тогава дойде щастието - контрольорът влезе!
Отнасяйте се към „късметлийските билети“ като към начин да прекарате малко времето на пътуването с аритметични упражнения и като допълнителна причина да му се зарадвате.
Между другото, обърнете внимание на татковците и майките: много е полезно да разказвате на децата за такива упражнения. В училище не обичат да смятат наум, така че нека поне да се забавляват в тролейбусите, като събират или умножават числа. И това няма да навреди и на възрастните: както в ред, така и през един, усвоявайки понятията паритет, симетрия, множественост ... И също така не можете да забравите за изваждане с деление. Във всеки случай, за развитието на детето, такива забавни пъзели няма да навредят.
И ако нямате късмет с билет - не се обезсърчавайте! По улицата се движат толкова много коли с "щастливи числа"!
Успех за вас и щастие!
"Честит билет"
Всички сме в транспорта. На път за работа, дом, място за почивка и
и т.н. И много често купуваме билет, който има в повечето
случаи шестцифрено число. Чрез добавяне на първите три цифри от номера на билета и
сравнявайки ги със сумата от втората тройка числа, ние определяме "щастие"
този билет. С "щастливо" число всичко е повече или по-малко ясно и
повечето знаят. Какво ще кажете за други ненулеви числа? Това е ясно
разликата в числата варира от 0 до 27. Ето как се роди този таблет ...
Действието на билета е тривиално (между другото, изобщо не е необходимо да го ядете!) -
билетът е валиден 24 часа от момента на активиране или до покупката
следващ билет с безсмислен номер. Активиране на билети
възниква след преброяване на числото и осъзнаване на значението му – т.н
да речем, магически ритуал.
(Забележка: Ако следващият билет има самостоятелно значение, а
предишният все още не е угасен - една стойност се наслагва върху друга. Добре,
например - взехте билет с разлика в числата = 1 = - което означава
дата. Прехвърлен на друг транспорт, без да срещам никого познат -
тоест тикетът все още е активен и не е "работил". Взеха нов билет - и
него разликата на цифрите = 7 = - това е вар. И така, какво или може да се случи
две събития, или те се сливат в едно - на среща, която все пак ще получите
новини ("Бременна съм!" - шега ...). Е, и така нататък. Комбинации от
поредици от три числа не са тествани от авторите - няма големи
статистически данни при шофиране с три трансфера - рядкост,
разбирам).
Тази схема се определя емпирично. Както във всеки експеримент
Наистина са възможни грешки. Изпратете вашите наблюдения и те ще го направят
взети предвид следващия път.
Тълкуване на значението на разликата в цифрата
0 Късмет Всеки замислен бизнес ще завърши успешно или вие
нещо явно е добро.
1 среща Ще срещнете човек, когото ще се радвате да видите (среща
лично, а не работно).
2 Среща Ще имате бизнес среща.
3 Повторение Нещо ще трябва да се повтори, иначе няма да работи.
4 Предупреждение Бъдете внимателни! Днес може да закъснеете до момента
дестинация! Не се отпускайте и всичко ще бъде наред. Но ако зяпнеш -
късно гарантирано!
5 Приятност Една приятна среща или събитие ще подобри настроението ви!
6 Неприятности Неприятна среща или събитие може да ви развали
настроение. Не се притеснявайте много!
7 Съобщение Ще получите новини от някого!
8 Хаос Нещо днес няма да може да расте заедно, да закачи, да завърши ...
9 Завършване Някои започнати дейности днес ще бъдат затворени напълно.
10 Започнете Днес ще започнете нов проектили нова мисъл ще те осени,
идея.
11 Разходка Е, или задръстване, или просто трябва да се разходите ...
12 дузини Възможност за пиене на алкохол...
13 Дяволската дузина
държави...
14 Не означава нищо
15 означава нищо
16 Не означава нищо
17 Не означава нищо
18 Не означава нищо
19 Не означава нищо
20 означават нищо
21 Не означава нищо
22 означава нищо
23 Не означава нищо
24 не означава нищо
25 Повторение Нещо ще трябва да се повтори, иначе няма да работи.
26 Среща Имате бизнес среща.
27 Среща Ще срещнете човек, когото ще се радвате да видите
(лична среща, не на работа).
Колко начина има да платите 50 цента? Смятаме, че можете да платите с 1 пени, 5 монети, 10 стотинки, 25 четвърти и 50 половин долара. György Pólya популяризира този проблем, като демонстрира инструктивен начин за решаването му с помощта на генериращи функции.
Нека напишем безкрайна сума, представяща всички възможни начини за размяна. Най-лесно е да започнем, когато има по-малко разновидности на монети, така че нека започнем, като кажем, че нямаме други монети освен едно пени. Сумата от всички начини за плащане на определена сума стотинки (и само стотинки) може да бъде записана като
тъй като всяка опция за изплащане включва няколко монети, избрани от първия множител, и няколко пенита, избрани от П. (Забележи, че н не е равно 1 + 1 + 5 + (1 + 5 ) 2 + (1 + 5 ) 3 + ..., тъй като тази сума включва много видове плащания повече от веднъж. Например терминът (1 + 5 ) 2 = 1 1 + 1 5 + 5 1 + 5 5 третира 1 5 и 5 1 като различни, но ние искаме да изброим всички комплекти монети веднъж, независимо от техния ред. )
По същия начин, ако позволим и стотинки, получаваме безкрайна сума
Нашата задача е да намерим колко члена в ° Сструва точно 50 цента.
Проблемът се решава с помощта прост трик. Нека заменим 1 с z, 5 пер z 5, 10 на z 10, 25 на z 25 и 50 нататък zпетдесет . След това всеки термин се заменя с z n, където нцената на оригиналния термин в стотинки. Например терминът 50 10 5 5 1 ще се превърне в z 50+10+5+5+1 = z 71 . Всеки от четирите възможни начиниплащат 13 цента, а именно 10 1 3 , 5 1 8 , 5 2 1 3 и 1 13 , се свежда до z 13; следователно, коефициентът при z 13 след z- смените ще бъдат 4.
Позволявам Пн нн дн Q n и ° С n обозначава броя на начините за плащане на сумата нцента, ако можете да използвате монети не по-стари, съответно 1, 5, 10, 25 и 50 цента. Нашият анализ показа, че тези числа са коефициенти при z nв съответната степенна серия
| П = | 1 + z + z 2 + z 3 + z 4 + ... , |
| н = | (1 + z 5 + z 10 + z 15 + z 20 + ...)П, |
| д = | (1 + z 10 + z 20 + z 30 + z 40 + ...)н, |
| Q = | (1 + z 25 + z 50 + z 75 + z 100 + ...)д, |
| ° С = | (1 + z 50 + z 100 + z 150 + z 200 + ...)Q. |
Очевидно е, че П н= 1 за всички н≥0. При кратък размисъл е лесно да се докаже това н н = [н/5] + 1: за добавяне до нцента от пенита и монети, трябва да вземем 0, или 1, или..., или [ н/5] никела, след което има само един начин да изберете необходимия брой пенита. Така че ценностите П ни н нлесно за изчисляване, но д н , Q ни ° С нвъпросът е много по-сложен.
Един от подходите за изследване на тези формули се основава на наблюдението, че 1 + z m + z 2м+ ... има само 1/(1 z m). Следователно можем да пишем
Сега, приравнявайки коефициентите при z nв тези уравнения получаваме рекурентни отношения, от които лесно се изчисляват желаните коефициенти:
Например коефициентът при z nв д= (1 z 25)Qсе равнява Q н Q н 25; така и трябва да бъде Q н Q н 25 = д н, както е написано по-горе.
Би било възможно тези отношения да бъдат разкрити и изразени Q н, например във формата Q н = д н + д н 25+ д н 50+ д н 75 + ..., където сборът свършва, когато индексите станат отрицателни. Въпреки това, оригиналната, неитеративна форма е удобна с това, че всеки коефициент се изчислява само с едно събиране, както в триъгълника на Паскал.
Ние използваме тези отношения, за да намерим ° Спетдесет . първо, ° С 50 = ° С 0 + Q 50, така че трябва да знаем Qпетдесет . Освен това, Q 50 = Q 25 + д 50 и Q 25 = Q 0 + д 25; така че и ние се интересуваме д 50 и д 25 . Тези ценности д нна свой ред зависят от д 40 , д 30 , д 20 , д 15 , д 10 и д 5 и от н 50 , н 45 , ..., н 5. По този начин, за да се определят всички необходими коефициенти, е достатъчно да се извършат прости изчисления:
| н | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |
| P n | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| N n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| D n | 1 | 2 | 4 | 6 | 9 | 12 | 16 | 25 | 36 | ||
| Qn | 1 | 13 | 49 | ||||||||
| C n | 1 | 50 | |||||||||
Отговорът е в долната част на таблицата. ° С 50: Има точно 50 начина да дадете бакшиш от 50 цента.
Какво може да се каже за затворената форма за ° С н? Умножаването на всички уравнения ни дава компактен израз за генериращата функция
кое е рационална функцияот z, чийто знаменател има степен 91. По този начин можем да разложим знаменателя на 91 фактора и да изразим ° С нв "затворена форма", състояща се от 91 члена. Но такова ужасно изражение не се качва в никакви порти. Възможно ли е да се намери нещо по-добро в този конкретен случай, вместо да се прилага общият метод?
И тук е първият искрица надежда: ако в ° С(z) замени 1/(1 z) до (1 + z + z 2 + z 3 + z 4)/(1 z 5):
след това степента на знаменателя на "компресираната" функция Č (z) вече е само 19, така че тази функция е много по-добра от оригиналната. Нов израз за ° С(z) показва по-специално това ° С 5н = ° С 5н+1 = ° С 5н+2 = ° С 5н+3 = ° С 5н+4 ; наистина това съотношение е лесно за обяснение: има точно толкова начини да дадете 53 цента, колкото и 50 цента, тъй като броят на пенитата по модул 5 е известен предварително.
Въпреки това, дори и за Č (z) не съществува прост израз, въз основа на корените на знаменателя. Вероятно, най-простият начинизчисления на коефициенти Č (z) се получава, като се отбележи, че всеки множител в знаменателя е делител на 1 zдесет Следователно можем да пишем
Тук, за пълнота, е разширен израз за А(z):
(1 + z + ... + z 9) 2 (1 + z 2 + ... + z 8)(1 + z 5) =
= 1 + 2z + 4z 2 + 6z 3 + 9z 4 + 13z 5 + 18z 6 + 24z 7 +
+ 31z 8 + 39z 9 + 45z 10 + 52z 11 +57z 12 + 63z 13 + 67z 14 + 69z 15 +
+ 69z 16 + 67z 17 + 63z 18 + 57z 19 + 52z 20 + 45z 21 + 39z 22 + 31z 23 +
+ 24z 24 + 18z 25 + 13z 26 + 9z 27 + 6z 28 + 4z 29 + 2z 30 + z 31 .
И накрая, използвайки факта, че
получаваме следния израз за коефициентите Č нна градуси z nв разширяването на функцията Č (z), при което н = 10р + rи 0≤ r<1 0:
| Č 10р+r = | ∑ | А й | ( | к + 4 к |
) | = | ||||||||||||||||
| й, к 10к+й=н |
||||||||||||||||||||||
| = А r | ( | р + 4 р |
) | + А r+10 | ( | р + 3 р |
) | + А r+20 | ( | р + 2 р |
) | + А r+30 | ( | р + 1 р |
) | . |
Това всъщност съдържа 10 различни случая, по един за всяка стойност r; но все още е добра затворена формула в сравнение с алтернативи, включващи степени на комплексни числа.
Използвайки този израз, можем да намерим например стойността ° С 50р = Č 10р. Тук r=0 и имаме
за сума от 1 долар, се оказва
| ( | 6 4 |
) | + 45 | ( | 5 4 |
) | + 52 | ( | 4 4 |
) | = 292 начина; |
и за милион долара това число ще бъде
| ( | 2000004 4 |
) | + 45 | ( | 2000003 4 |
) | + 52 | ( | 2000002 4 |
) | + 2 | ( | 2000001 4 |
) | = |
= 66666793333412666685000001.
