Eto zadacha 5, koiato se nadiavam da se haresa poveche na 1 momiche, makar veche da sym pochti siguren che ne moje da i se ugodi:
Zadacha 4(trudnost 8)
Domakinia, chakashta gosti, im e izpekla keks. Tia znae, che shte doidat ili p ili q na broi gosti, kato p i q sa vzaimno prosti. Vyprosyt e na kolko nai-malko (ne nepremenno ednakvi) parcheta moje da se razreje predvaritelno keksa, taka che da mowe da byde razpredelen i na p, i na q ravni chasti. Mai ne stana mnogo iasno, zatova dopylvam s trivialnoto reshenie - pq ravni chasti, ako doidat p gosti, vseki poluchava q parcheta i obratno.
Haide nasluka.

Редактирано от Heдeв на 02.10.02 19:21.

izbirame p < q
pravim [q/p]*p na broy par4eta po 1/q 4asti (izpolzvam tvoeto ozna4enie [.])
ostanalata 4ast ((q%p)/q) ot tortata delim po s'6tiya algorit'm taka 4e da moje da se razdeli mejdu p i q%p gosti (tuk % ozna4ava ostat'k pri deleneto)

recursivno re6enie - recursivna formula
f(p,1) = f(p,0) =p
f(p,q) = [q/p]*p + f(q%p,p) ; ako p < q, ina4e obratno

pove4e ne moga
spi mi se

s pove4e humor mu e maykata

Edno wyzmozno reshenie (ne pretendiram, che e prawilnoto):

Neka p < q
Izbirame:
p parcheta s razmer 1/q
(q-p)p parcheta s razmer 1/pq

Obsht broj parcheta: p + (q-p)p = p(1+q-p).

Kak gi razpredeljame:
p dushi: Razdawame po edno parche s razmer 1/q i po (q-p) parcheta s razmer 1/pq.
q dushi: Razdawame na p dushi po edno parche s razmer 1/q, a na ostanalite (q-p) dushi po p parcheta s razmer 1/pq.

v obshtia sluchai reshenieto e

p+q - NOD(p,q)

poneje p i q sa vzaimno prosti, to v sluchaia reshenieto e

p+q-1

ostaviam obiasneniyata za niakoi po-entusiaziran ot men..

1 momiche

Dokato eksperimentirah, ustanowih che towa koeto napisah moze da se podobri:
Wmesto da izbiram samo p, moga da izbera p*[q/p] parcheta s razmer 1/q.
I wmesto da izbera (q-p)p, moga da izbera (q-p*[q/p])p parcheta s razmer 1/pq
Taka poluchawam obshto p(q+(1-p)*[q/p]) parcheta, koeto e po-malko ot predishnoto p(q+(1-p)).
Razpredeljaneto e slednoto:
p dushi: Po p*[q/p] parcheta s razmer 1/q i (q-p*[q/p]) parcheta s razmer 1/pq.
q dushi: Na p*[q/p] dushi parcheta s razmer 1/q, a na ostanalite po p parcheta s razmer 1/pq.

Elementarna transportna zada4a
Neka priemem 4e keksa ima lice p*q nekvi edinici
Pravim Matri4ka s razmeri p i q
Ame imame p sklada i q magazina.....
a1,a2,a3,....ap SUM
b1
b2
......
bq
------------------
sum q,q,q,.......obsto p*q
Elemettarna transportna zada4a, kydeto wsi4ki koeficienti sa ravni. Prosto gi razpredeliame po metoda na gornia liav ygyl.
Izvestno ot analiza e, 4e transp. zada4a ima maximum p+q-1 Nenulevi elementi

tochno taka! :-))

A mojesh li da kajesh kak namerih formulata za obshtia sluchai?

но предполагам, че като си написала поредната програмка си забелязала тази зависимост. Това, разбира се, в рамките на шегата.
Трябва, разбира се, да се отбележи, че в нашият случай при взаимно прости p и q, p+q-1 e най-малкият брой. В общия случай на трансп. задача планът в някой момент може да се "изроди" и да съдържа по-малко от p+q-1 ненулеви.
Това може да стане, ако .....как да го формулирам....абе ако сборовете по няколко хоризонтала и верикала съвпаднат преди края. В нашият случай това няма как да стане. Ако p и q имат НОД>1, плана ще се изроди точно НОД-1 пъти (последното не е израждане), така че ще получим най-малък брой
p+q-1-(НОД-1). Или с други думи голямата таблица може да се раздели на НОД независими таблици с размери p/НОД и q/НОД. Тогава пак общият брой ненулеви става
НОД*(p/НОД+q/НОД-1)=p+q-НОД

Този път купата е за теб заради обосновката.

ne viarvam na sunenite si ochi!!!!

dade mu kupata zatova che za da stigne ot edinia krai na Varna do drugia minava za po-napriako prez Belgrad li?!

ami tova che reshih zadachkata v obshtia sluchai (i to samo s logicheski instrumentarium) - ne mi li nosi tochki?