Եթե վերաձևակերպեմ լուծումը, F(i)-ով կարելի ա նշանակել ծնվածների թիվը i-րդ տարում: Վերջնական պատասխանը կլինի 1-ից 35 տարի առաջ ծնվածների գումարը: Իսկ i-րդ տարում ծնվածների գումարը կլինի 15-34 տարի առաջ ծնվածների գումարը` մոտավորապես.
F(i) = F(i - 34) + F(i - 33) + ... + F(i - 15)
Հիմա եթե ունենք առաջին 35 տարիների հաշվարկը (F(1)-ից F(35)), դրանից կարող ենք F(2)-ից F(36)-ը ստանալ {F(1);F(2);...;F(35)} վեկտորը մատրիցով բազմապատկելով.
կամ ինչ-որ սենց բանԿոդ:0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
Դե էս մատրիցն էլ O(logN)-ում կարանք N աստիճան բարձրացնենք:
Ժողովուրդ ինչի եք բարդացնում?
Բավարար է, որ պահեք մի հատ միաչափ զանգված, էլէմենտների քանակը նախապես չսահմանած` ցուցիչով, որտեղ ամեն էլէմենտի արժեքը կլինի տվյալ կենթադու տարիքը:
Հետո ըստ տարիների ցիկլով անցնում ենք էդ զանգվածի վրայով:
Եթե կենդանի սեռահասուն է (15<=k<=35), ապա զանգվ ածում մեկ տարր ավելացնում ենք ու իրա տարիքը դնում 1, քանակը մի հատով ավելացնում:
Եթե կենդանին 35 է, ուրեն տարիքը դնում ենք զրո` սատկել է ու քանակը մի հատ հանում:
Ցանկացած տարիների համար էլ աշխատում է` տրիվյալ լուծում է, բայց կարծում եմ կարելի է օպտիմիզացնել
••Սեղմել՝ ցույց տալու համար
Ոնց լուծում ա?
Կհաշվի?
Հ.Գ.
Շատ մեծ թվերի պարագայում ճիշտ կլինի որոշ int-եր փոխարինել long-երով:
Baseic-ում նման խնդիրը շատ հեշտ լուծվում է Dictionary տիպի օբյեկտով` յուրաքանչյուր էլէմենտը կենդանի է: Ցիկլով ֆռում ես` հենց "վախտը հասավ" սատկացնում ես` էլեմենտը ջնում ես, իսկ ետե սեռահասուն է` էլէմէնտ ես ավելացնում:
C#-ում էդ Dictionary-ները օգտագործել եմ, բայց C++ում` ձևը չգիտեմ![]()
Վերջին խմբագրող՝ Varzor: 10.04.2012, 11:18:
Լոխ մունք ենք, մնացածը` լոխ են...
Զանգվածի մեծությունը փաստորեն տվյալ տարվա դրությամբ երբևիցե ապրած կենդանիների քանակն ա, չէ? Բայց մի քանի 100 տարուց ապրող կենդանիների քանակը էնքան մեծ ա դառնում, որ 64 բիտանոց long long-ն էլ չի հերիքում քանակը պահելու համար: Այսինքն ուղղակի սիմուլյացիա ես անում ու պատասխանը շատ հեշտ ստացվում ա, բայց մի քիչ մեծ թվերի համար համ շատ երկար ա աշխատում, համ էլ էդքան հիշողություն չի գտնվի բոլորի տարիքները հիշելու համար:
Իմ վերջին լուծումը (կոդով), օրինակ, հիշողություն շատ քիչ ա օգտագործում ու օգտագործումն էլ N-ից կախված չի, բայց համեմատաբար դանդաղ ա աշխատում (N=1,000,000,000-ի համար մոտ 450 վրկ.): Իսկ էս ամենավերջին նկարագրածս լուծումը 0.5 վրկ.-ի մեջ կտեղավորվի նույնիսկ N=10^12-ի դեպքում:
Ի դեպ, էդ ցուցիչի հետ սխալ ես աշխատում: Ցուցիչը հայտարարելուց, իրա արժեքը ինչ-որ անկապ թիվ ա (հիշողության մեջ անկապ տեղ ա ցույց տալիս), հաշվի առնելով էլ, որ զանգվածի երկարությունը ուզում ես դինամիկ փոխել, լավ կլինի std::vector-ից օգտվես.
vector<int> vi;
vi.push_back(a);
Dictionary-ն էլ C++ ում std::map-ն ա`
map<string, int> m;
m["tandz"] = 121;
m["khndzor"] = 367;
cout << m["tandz"] + m["khndzor"] << endl;
Varzor (10.04.2012)
Հա, ճիշտ ես հասկանում` գրածս ծրագրում n-ը (k զանգվածի տարրերի քանակը) երբևէ ապրած կենդանիների քանակն է:
Որպես օպտիմիզացիա կարելի է ընդամենը ամեն տարի 0-ական տարրերը զանգվածից հեռացնել` կմնան մենակ չսատկած կենդանիները:
Կարելի է երկրորդ զանգվածը պահել` ոչ սեռահասուն կենդանիների համար:
Եղբայր էդ ինչ թիվա, որ 64 բիտանոց long-ը չի հերիքի? 2-ի 63 Աստիճանից մեծ` 8x10246? էսի քո ասած 1012-ից հաստատ մեծ թիվ ա
Ցուցիչի հետ հեչ էլ սխալ չեմ աշխատում` դասական աշխատելու ձևն է: Ինչ կապ ունի, թե ինչ թիվա? փոփոխական է, կարևորը որ հետո արժեք տաս: Մի քանի գրառում առաջ Դեյտելի գրքից նույնիսկ մեջբերում եմ արել դրա հետ կապված
Հեչ իմաստ չեմ տեսնում vector օբյեկտից օգտվելու մեջ` ցուցիչը լիովին բավարար է:
Dictionary-ն էլ հեչ էլ map-ը չի:
Dictionary-ն Microsoft Scripting Runtime գրադարանի օբյեկտ է` որ լեզուն հնարավորութուն ունի այդ գրադարանին դիմելու` կարող ես հայտարարել:
Կառուցվածքն էլ հետևյալն է.
D (key, value) ու value-ն կարող են լինել ցանկացած տիպի, նույնիսկ այլ օբյեկտ:
Չեմ կարծում, որ մատրիցաների բազմապատկումը մեծ թվերի պարագայում կարող է այդքան արագ լինել` 900 անգամ:
Ամեն դեպքում քո առաջարկած տարբերակը շատ հետաքրքիր ու ուսանելի տարբերակ է:
Ի դեպ 100 տարում կենդանիների քանակը ստացվում է 1703208 հատ` կենդանի, չսատկած: Ու հաշվում ա 73 վայրկյանում:
Էս էլ կոդը` VBA-ի համար, կարող ես Excel-ի կամ Word-ի մեջ աշխատացնել: Ընդ որում սա Dictionary-ով տարբերակը չի
Կոդ:Sub Test1() Dim tari, qanak, n, i, j As Long Dim k() As Variant Dim StartTime As Date Dim EndTime As Date Dim delta As Date Dim s As String tari = 100 ReDim k(1) As Variant k(0) = 15 qanak = 1 n = 1 StartTime = Now For i = 1 To tari For j = 0 To n - 1 If k(j) > 0 Then If (k(j) >= 15 And k(j) <= 35) Then n = n + 1 ReDim Preserve k(n) As Variant k(n - 1) = 1 qanak = qanak + 1 ElseIf k(j) = 35 Then k(j) = 0 qanak = qanak - 1 End If k(j) = k(j) + 1 End If Next j Next i EndTime = Now delta = EndTime - StartTime s = CStr(Hour(delta) * 3600 + Minute(delta) * 60 + Second(delta)) MsgBox (CStr(qanak) & " kendani <->" & s & " seconds") End Sub
Լոխ մունք ենք, մնացածը` լոխ են...
N=360-ի համար, պատասխանը (այսինքն` 360-րդ տարում ապրողների քանակը) 8,508,275,536,357,516,150 ա: N=370-ի պատասխանը long long-ում տեղ չի անում: Էտքան հիշողություն էլ, բնականաբար, չկա:Եղբայր էդ ինչ թիվա, որ 64 բիտանոց long-ը չի հերիքի? 2-ի 63 Աստիճանից մեծ` 8x10246? էսի քո ասած 1012-ից հաստատ մեծ թիվ ա:
Ո՞նց սխալ չես աշխատում, եթե իմ մոտ runtime error ա տալիս քո կոդը: Ասում եմ` քո ցուցիչ-փոփոխականին նույնիսկ արժեք չես տալիս, գոնե գրեիր.Ցուցիչի հետ հեչ էլ սխալ չեմ աշխատում` դասական աշխատելու ձևն է: Ինչ կապ ունի, թե ինչ թիվա? փոփոխական է, կարևորը որ հետո արժեք տաս: Մի քանի գրառում առաջ Դեյտելի գրքից նույնիսկ մեջբերում եմ արել դրա հետ կապված
Հեչ իմաստ չեմ տեսնում vector օբյեկտից օգտվելու մեջ` ցուցիչը լիովին բավարար է:
int *k = new int[2000];
Բայց մեկ ա շատ շուտ ապրող կենդանիների քանակը 2000-ից անցնելու ա (ու հասնելու ա վերոհիշյալ long long-ում չտեղավորվող թվերի) ու էդ դեպքում k[j] արտահայտությունը, որտեղ j >= 2000 runtime error ա: Էդ դեպքում էլ պիտի նոր հիշողություն վերցնես ու հնից copy անես նորը.
Կոդ:int *t = k; k = new int[4000]; memcpy(k, t, sizeof(int)*2000); delete[] t;Ես ի նկատի չունեի, որ std::map-ը Microsoft Scripting Runtime-ի Dictionary ա, այլ որ std::map-ը dictionary տեսակի data structure ա, էլի ունի map<key, value> տեսքը ցանկացած տիպի key-ի ու value-ի համար (պայմանով, որ key-ի վրա համեմատության օպերատոր կա սահմանած):Dictionary-ն էլ հեչ էլ map-ը չի:
Dictionary-ն Microsoft Scripting Runtime գրադարանի օբյեկտ է` որ լեզուն հնարավորութուն ունի այդ գրադարանին դիմելու` կարող ես հայտարարել:
Կառուցվածքն էլ հետևյալն է.
D (key, value) ու value-ն կարող են լինել ցանկացած տիպի, նույնիսկ այլ օբյեկտ:
KxK չափի երկու մատրիցների բազմապատկումը տրիվիալ ալգորիթմով O(K^3) ժամանակային բարդություն ունի: Մեր խնդրում K-ն կոնստանտ ա (K=35), իսկ հենց "մատրիցի բազմապատկում" գործողությունների քանակը O(logN) ա (N=10^12-ի դեպքում մոտ 40): Այսինքն պետք ա լինում 40 անգամ (35^3)*ինչ-որ-ոչ-շատ-մեծ-կոնստանտ քանակի գործողություններ կատարել, որը հանգիստ կտեղավորվի 0.5 վրկ-ի մեջ: Իսկ եթե ի նկատի ունես կենդանիների քանակը նկարագրող թվերի մեծ լինելը, ապա soultaker-ի առաջարկած խնդրում պետք ա տալ (պատասխան MOD 1000003), ինչը նշանակում ա, որ բոլոր միջանկյալ բազմապատկումներից ու գումարումներից հետո կարելի ա MOD 1000003 անել ու չանհանգստանալ մեծ թվերի մասին:Չեմ կարծում, որ մատրիցաների բազմապատկումը մեծ թվերի պարագայում կարող է այդքան արագ լինել` 900 անգամ:
Varzor (10.04.2012)
Այս պահին թեմայում են 4 հոգի. (0 անդամ և 4 հյուր)
Էջանիշներ