Dixtosa ![]() Eშისაიდან მოვიდა 3**13?ისე 4 * 52 * 3**13 = 331M+ ...
|
Quick ![]() Upsolving ჩაირთო...
|
saba_tavdgiridze ![]() აღარ მინდა.:)...
|
saba_tavdgiridze ![]() B ამოცანის 17 ტესტს ვერ მიმანიშნებთ?...
|
tornike5 ![]() ვაპირებდი იგივე მეკითხა მარა მეგონა უეჭველი იქნება...
|
giorgi123 ![]() მადლობა.შარშან ფინალში ამოცანების ყურებით ვიფარგლე...
|
Elle ![]() შარშან ფინალს codeblocks-ით წერდით?დავაყენეთ codeb...
|
მე პირადად არ გამომიყენებია k>3 შემთხვევებში ფორმულა, თუმცა ამ თემაში ვისაუბრებ თუ როგორ შეიძლება ამ ფორმულების მიღება. პროგრამულად, ნებისმიერი f(n,1), f(n,2), ... , f(n,k)-სთვის პრეკალკულაციას ჭირდება O(k^3) დრო და O(k^2) მეხსიერება, და შემდეგ f(n,k) ითვლება O(k) დროში. თუმცა, უბრალოდ საინტერესოა, სუფთა თეორიაში, ქაღალდზე, როგორ გამოვიყვანოთ ეს ფორმულები. ცნობისათვის,
(სხვათა შორის, შეამჩნევდით, რომ f(n,3)=f(n,1)^2. ძალიან საინტერესო ტოლობაა, სკოლის ასაკში შეიძლება შეგხვედრიათ და ამოგიხსნიათ კიდეც).
მაშ ასე, დავიწყოთ დამტკიცება! მოდით განვიხილოთ რისი ტოლია
ახლა გამოვიყენებთ ფორმულას
და მივიღებთ, რომ
ეს ყველაფერი კაია, მაგრამ გაგიჩნდებათ კითხვა, აქედან სასარგებლოს რას ვღებულობთ ჩვენი ამოცანისთვის :D
მოდით დავითვალოთ რისი ტოლია n^(k+1).
ახლა გამოვთვალოთ f(n,k).
რადგანაც
ამიტომ
შევნიშნოთ, რომ განტოლების მარჯვენა მხარეს ყოველი f(n,x) ფუნქციაში, x<k. მეტიც, ჩვენ ვიყენებთ მხოლოდ f(n,1), f(n,2), f(n,3), ... , f(n,k-1). ამიტომ დავიწყოთ იქიდან, რომ f(n,0)=1^0+2^0+...+n^0=n. და k-ს ზრდის მიხედვით ავყვეთ. მივიღებთ ფუნქციას ყველა k-სთვის :)
ვისაც ეს ფორმულა ურჩხული გგონიათ, ძალიან ცდებით. მოდით გამოვიანგარიშოთ f(n,1), f(n,2), f(n,3). საინტერესო იქნება f(n,4)-ის მნიშვნელობის გამოთვლა, რომელიც მეც არ ვიცი ჯერჯერობით, თუმცა დაპოსტვის შემდეგ მეცოდინება :)
საინტერესოა რა იქნება f(n,4)-ის ფორმულა :)
აჰა! ვიწვალე და გამოვთვალე :)
პროგრამულად ამის გაკეთებას თქვენვე მოგანდობთ ;)