BG Development


  Reply to this topicStart new topicStart Poll

> Задачка от книгата на Наков, Задачката за огърлицата
sgeorgiev
Публикувано на: 06-10-2017, 11:09
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 4
Регистриран на: 06.10.17



***

Това мнение е било редактирано от sgeorgiev на 06-10-2017, 13:05
PMEmail Poster
Top
wqw
Публикувано на: 06-10-2017, 11:22
Quote Post


Group Icon
Име: Владимир Висулчев
Група: VIP
Ранг: Почетен член

Мнения: 5616
Регистриран на: 10.06.04



Задача 1.195. Огърлица
Огърлица се състои от бели и черни мъниста така, че няма две съседни черни мъниста (виж фигура 1.5.2е.).

QUOTE (Фигура 1.5.2е. Мъниста.)

user posted image

Ако n е броят на черните мъниста, а k — на белите, какъв е броят на различните огърлици, които могат да бъдат образувани от мънистата? Напишете програма за генериране на t различни огърлици, по дадено естествено число t.


QUOTE (sgeorgiev @ 06-10-2017, 11:09)
2. Как би трябвало да се реши задачата така че да не се получават тези повторения "1 0 1 0 0" и
"1 0 1 0 0"?

По големият ти проблем е че `1 0 1 0 0` е повторено като `0 0 1 0 1`, ако ме разбираш. . .

Със сигурност бройката може да се сметне аналитично и това се търси (математика), не въртене на цикли.

cheers,
</wqw>

Това мнение е било редактирано от wqw на 06-10-2017, 17:19


--------------------
PMEmail PosterUsers Website
Top
sgeorgiev
Публикувано на: 06-10-2017, 12:13
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 4
Регистриран на: 06.10.17



***

Това мнение е било редактирано от sgeorgiev на 06-10-2017, 13:05
PMEmail Poster
Top
Дон Реба
Публикувано на: 06-10-2017, 12:40
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 5595
Регистриран на: 11.11.06



QUOTE (sgeorgiev @ 06-10-2017, 12:13)
"1 0 1 0 0" и "0 0 1 0 1" са различни. Според мен има значение на кой край на редицата са черните топчета. Дори и да допуснем че е проблем то той в никакъв случай не е голям. Просто премахваме реда add(0, WHITE, n, k); и така наречените повтарящи се решения изчезват.

пробвал ли си с реална огърлица?
PM
Top
sgeorgiev
Публикувано на: 06-10-2017, 12:45
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 4
Регистриран на: 06.10.17



***

Това мнение е било редактирано от sgeorgiev на 06-10-2017, 13:04
PMEmail Poster
Top
wqw
Публикувано на: 06-10-2017, 12:50
Quote Post


Group Icon
Име: Владимир Висулчев
Група: VIP
Ранг: Почетен член

Мнения: 5616
Регистриран на: 10.06.04



QUOTE (sgeorgiev @ 06-10-2017, 12:13)
"1 0 1 0 0" и "0 0 1 0 1" са различни. Според мен има значение на кой край на редицата са черните топчета.

Напротив, иначе задачата нямаше да се казва "Огърлица". Като са в кръг, всяко топче може да е начало на твоите редици, т.е. при тебе всяка ротация на A B C D е същата огърлица. Сега, ако задачата се казваше "Огърлица с възел" ротациите нямаше да са еквивалентни. . .

Обикновено в такъв род задачи търсиш някаква еквивалентна трансформация, която ще ти позволи да решаваш някаква много по-проста задача. В случая е много полезно да кодираш огърлиците като "брой бели топчета след черното минус едно" понеже нямаш две черни последователно. Примерно твоето "1 0 1 0 0" се трансформира до "0 1", ето още примерни трансформации
CODE
1 0 1 0 1 0 0 0 0 -> 0 0 3
1 0 1 0 0 1 0 0 0 -> 0 1 2
1 0 1 0 0 0 1 0 0 -> 0 2 1
1 0 0 1 0 1 0 0 0 -> 1 0 2
1 0 0 1 0 0 1 0 0 -> 1 1 1

Какво получаваме от тази трансформация?
1. Сумата на ел. на такива редици от n черни и k бели е точно k - n което доста удобно
2. Броят ел. на такива редици е точно n (броят на черните)
3. Можем да генерираме огърлици като просто търсим редица от ест. числа с горните две свойства
4. За да не дублираме огърлици можем да подредим ротациите по "големина" и да избираме най-малката.

За бройката N(n, k) на огърлиците вече имаме че е | S(n, k - n) | / (k - n) където S(A, B) e множеството на редици от A ест. числа така че сумата им е точно B, а делителят от по-горе "обира" еквивалентните ротации.

Обратно, ако трябва да генерираме някакви t огърлици почваме да генерираме редиците от S(n, k - n) и за всяка редица проверяваме дали е най-малко по "големина" спрямо всичките си ротации. Ако е най-малка тогава правим обратната трансформации в 1 0 1 0 1 0 0 0 0 и печатаме -- тук най-важното е да не дублираме с вече отпечатана огърлица, това е месото на подусловието.

QUOTE (sgeorgiev @ 06-10-2017, 12:45)
Моля ако нямате отговори на въпросите или конструктивни предложения НЕ СПАМЕТЕ ТЕМАТА.

FYI, спамът в този форум е разрешен до нива преценени от модераторите. С подобни "предупреждения" ти самия нарушаваш правилата на форума, където е написано "НЕ СЕ ПРАВЕТЕ НА МОДЕРАТОРИ!". . .

cheers,
</wqw>

Това мнение е било редактирано от wqw на 06-10-2017, 12:56


--------------------
PMEmail PosterUsers Website
Top
Дон Реба
Публикувано на: 06-10-2017, 13:02
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 5595
Регистриран на: 11.11.06



QUOTE (sgeorgiev @ 06-10-2017, 12:45)
Моля ако нямате отговори на въпросите или конструктивни предложения НЕ СПАМЕТЕ ТЕМАТА.

верно ли, иначе какво, ще ни напляскаш? icon_smile.gif
PM
Top
sgeorgiev
Публикувано на: 06-10-2017, 13:03
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 4
Регистриран на: 06.10.17



***

Това мнение е било редактирано от sgeorgiev на 06-10-2017, 13:30
PMEmail Poster
Top
saruman
Публикувано на: 06-10-2017, 17:32
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 1564
Регистриран на: 21.07.10



Тази тема според мен трябва да се пин-не като важна,да се знае утре как да реагираш като ти дойде такъв селяндур на интервю,който не може да си преброи кокошките в двора,ама иначе велик алгоритмик и теоретик icon_mad.gif

Това мнение е било редактирано от saruman на 06-10-2017, 17:33


--------------------
http://www.wefunkradio.com/radio/

Remember,remember the fifth of November
PMEmail Poster
Top
SuN
Публикувано на: 07-10-2017, 11:06
Quote Post


Group Icon
Име: Финто Нешън
Група: Администратор
Ранг: Почетен член

Мнения: 4529
Регистриран на: 27.01.05



QUOTE (saruman @ 06-10-2017, 17:32)
като ти дойде такъв селяндур на интервю,който не може да си преброи кокошките в двора

Правилното е "като ти дойде такъв на интервю, на който магарета му излизат с едно повече като слезе от своето".

Постовете може да се цитират.

Не виждам каква е драмата. Тия въпроси не са за издевателства все пак, а за който има желание да помогне. Незнаещи и неразбиращи винаги ще има.

Това мнение е било редактирано от SuN на 07-10-2017, 11:09


--------------------
Копирай лесно ударено и - ѝ Ѝ
Замърсяване на въздуха в София - http://aqicn.org/city/bulgaria/sofia/druzhba/
PMEmail Poster
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2015 | BG Development | All Rights Reserved
RSS 2.0