[DSA] За приоритетните опашки, приоритетите и още нещо


4

Здравейте,

Като си пишех домашното за линейни структури много ми хареса 10-та задача: 

10.* We are given numbers N and M and the following operations:
a)N = N+1
b)N = N+2
c)N = N*2

Write a program that finds the shortest sequence of operations from the list above that starts from N and finishes in M. Hint: use a queue.

Решение с опашка не измислих, но се сетих за greedy algorithm - да вземем горната граница и да делим на 2 (ако е нечетно вадим едно), после да вадим 2 и накрая вадим 1 докато не стигнем долната граница. След това ги обръщаме. (И точно, когато щях да се зарадвам да постна решението- вече го имаше във форума :D)

Но не е това смисъла на post-a ми. Тази задача ми напомни много на една любима моя история за приоритетите в живота, която много силно ви препоръчвам да прочетете (няма да съжалявате): ТУК .

Не можах да намеря и продължението, но нека аз го довърша. След като професорът е напълнил вече буркана с пясък (това е n+1 -то :D)  ,пита дали е пълен и пак му отговарят с "Да". Тогава той излива 2 чаши кафе (или бира) и другия извод от това е: "Колкото и да сме си запълнили буркана (живота) винаги има място за 2 чаши кафе(бира) с приятел" .

Надявам се, че не съм ви отегчил много :D

Поздрави,

Събо :)

 

P.S. Решението на задачата от колегата: тук


Edit: решението не е вярно при случая, когато разликата е 2 -> Пример 1..3 резултата е 1,2,3, а отгора е 1,3. Трябва да има една допълнителна проверка.

 




Отговори



0
Аз я направих с рекурсия, но едвали ще е бързо за много елементи, мерси за темата.

от RamiAmaire (1868 точки)