User Tag List

Ցույց են տրվում 1 համարից մինչև 15 համարի արդյունքները՝ ընդհանուր 536 հատից

Թեմա: C++

Համակցված դիտում

Նախորդ գրառումը Նախորդ գրառումը   Հաջորդ գրառումը Հաջորդ գրառումը
  1. #1
    Ինժեներ soultaker-ի ավատար
    Գրանցման ամսաթիվ
    13.05.2010
    Գրառումներ
    221
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Մեջբերում MSGM-ի խոսքերից Նայել գրառումը
    Երկար հանրահաշիվ գրելու հավես չկա, բայց դրա վրա մտածել կարելի ա: Իմ գրած լուծումը փաստորեն O(N) ա, նույնիսկ եթե n-րդ անդամի համար ինչ-որ բանաձև գտնեմ, չգիտեմ O(N)-ից ավելի լավ ժամանակում կլինի հաշվել, թե չէ : Իսկ եթե պետք ա, որ մի 10 րոպեի մեջ տեղավորվի, գրածս լուծումը կարելի ա հեշտությամբ ձևափոխել, որ հիշողության օգտագործումը O(1) լինի:
    Կոդ:
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    #define MOD 1000000
    
    double getTime()
    {
    	return (double(clock())/CLK_TCK);
    }
    
    int F[2][40], N;
    
    int main()
    {
    	cin >> N;
    	double startTime = getTime();
    	F[0][15] = 1;
    	for (int i = 1, x = 1; i <= N; i++, x ^= 1)
    	{
    		int s = 0;
    		for (int j = 15; j < 35; j++)
    			s = (s + F[x ^ 1][j]) % MOD;
    		F[x][1] = s;
    		for (int j = 2; j <= 35; j++)
    			F[x][j] = F[x ^ 1][j - 1];
    	}
    	int ans = 0;
    	for (int i = 1; i <= 35; i++)
    		ans = (ans + F[x ^ 1][i]) % MOD;
    	cout << ans << endl;
    	cout << "Time: " << getTime() - startTime << endl;
    	return 0;
    }
    Իմ մոտ 450 վրկ. էր 1,000,000,000-ի համար:
    Դե ամբողջ հարցը դրանում է, ես մեծ դեպքի համար առաջարկում եմ O(logN) լուծում O(N)-ի փոխարեն (N-ը տարիներ քանակն է):

  2. #2
    Լիարժեք անդամ MSGM-ի ավատար
    Գրանցման ամսաթիվ
    02.09.2008
    Գրառումներ
    131
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Եթե վերաձևակերպեմ լուծումը, 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 աստիճան բարձրացնենք:

  3. Գրառմանը 2 հոգի շնորհակալություն են հայտնել.

    soultaker (09.04.2012), Varzor (10.04.2012)

  4. #3
    Ինժեներ soultaker-ի ավատար
    Գրանցման ամսաթիվ
    13.05.2010
    Գրառումներ
    221
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Մեջբերում MSGM-ի խոսքերից Նայել գրառումը
    Եթե վերաձևակերպեմ լուծումը, 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 աստիճան բարձրացնենք:
    Հենց դա էլ նկատի ունեի:

  5. #4
    Կեցցե թագավորը Varzor-ի ավատար
    Գրանցման ամսաթիվ
    16.03.2009
    Հասցե
    Երկիր մոլորակ, ՀՀ ք. Երևան
    Տարիք
    45
    Գրառումներ
    7,503
    Mentioned
    13 Post(s)
    Tagged
    0 Thread(s)
    Ժողովուրդ ինչի եք բարդացնում?
    Բավարար է, որ պահեք մի հատ միաչափ զանգված, էլէմենտների քանակը նախապես չսահմանած` ցուցիչով, որտեղ ամեն էլէմենտի արժեքը կլինի տվյալ կենթադու տարիքը:
    Հետո ըստ տարիների ցիկլով անցնում ենք էդ զանգվածի վրայով:
    Եթե կենդանի սեռահասուն է (15<=k<=35), ապա զանգվ ածում մեկ տարր ավելացնում ենք ու իրա տարիքը դնում 1, քանակը մի հատով ավելացնում:
    Եթե կենդանին 35 է, ուրեն տարիքը դնում ենք զրո` սատկել է ու քանակը մի հատ հանում:
    Ցանկացած տարիների համար էլ աշխատում է` տրիվյալ լուծում է, բայց կարծում եմ կարելի է օպտիմիզացնել
     •
    • 
     Սեղմել՝ ցույց տալու համար


    Ոնց լուծում ա?
    Կհաշվի?

    Հ.Գ.
    Շատ մեծ թվերի պարագայում ճիշտ կլինի որոշ int-եր փոխարինել long-երով:
    Baseic-ում նման խնդիրը շատ հեշտ լուծվում է Dictionary տիպի օբյեկտով` յուրաքանչյուր էլէմենտը կենդանի է: Ցիկլով ֆռում ես` հենց "վախտը հասավ" սատկացնում ես` էլեմենտը ջնում ես, իսկ ետե սեռահասուն է` էլէմէնտ ես ավելացնում:
    C#-ում էդ Dictionary-ները օգտագործել եմ, բայց C++ում` ձևը չգիտեմ
    Վերջին խմբագրող՝ Varzor: 10.04.2012, 11:18:
    Լոխ մունք ենք, մնացածը` լոխ են...

  6. #5
    Լիարժեք անդամ MSGM-ի ավատար
    Գրանցման ամսաթիվ
    02.09.2008
    Գրառումներ
    131
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Զանգվածի մեծությունը փաստորեն տվյալ տարվա դրությամբ երբևիցե ապրած կենդանիների քանակն ա, չէ? Բայց մի քանի 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;

  7. Գրառմանը 1 հոգի շնորհակալություն է հայտնել.

    Varzor (10.04.2012)

  8. #6
    Կեցցե թագավորը Varzor-ի ավատար
    Գրանցման ամսաթիվ
    16.03.2009
    Հասցե
    Երկիր մոլորակ, ՀՀ ք. Երևան
    Տարիք
    45
    Գրառումներ
    7,503
    Mentioned
    13 Post(s)
    Tagged
    0 Thread(s)
    Մեջբերում MSGM-ի խոսքերից Նայել գրառումը
    Զանգվածի մեծությունը փաստորեն տվյալ տարվա դրությամբ երբևիցե ապրած կենդանիների քանակն ա, չէ? Բայց մի քանի 100 տարուց ապրող կենդանիների քանակը էնքան մեծ ա դառնում, որ 64 բիտանոց long long-ն էլ չի հերիքում քանակը պահելու համար: Այսինքն ուղղակի սիմուլյացիա ես անում ու պատասխանը շատ հեշտ ստացվում ա, բայց մի քիչ մեծ թվերի համար համ շատ երկար ա աշխատում, համ էլ էդքան հիշողություն չի գտնվի բոլորի տարիքները հիշելու համար:

    Հա, ճիշտ ես հասկանում` գրածս ծրագրում n-ը (k զանգվածի տարրերի քանակը) երբևէ ապրած կենդանիների քանակն է:
    Որպես օպտիմիզացիա կարելի է ընդամենը ամեն տարի 0-ական տարրերը զանգվածից հեռացնել` կմնան մենակ չսատկած կենդանիները:
    Կարելի է երկրորդ զանգվածը պահել` ոչ սեռահասուն կենդանիների համար:
    Եղբայր էդ ինչ թիվա, որ 64 բիտանոց long-ը չի հերիքի? 2-ի 63 Աստիճանից մեծ` 8x10246? էսի քո ասած 1012-ից հաստատ մեծ թիվ ա
    Մեջբերում MSGM-ի խոսքերից Նայել գրառումը
    Իմ վերջին լուծումը (կոդով), օրինակ, հիշողություն շատ քիչ ա օգտագործում ու օգտագործումն էլ 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;
    Ցուցիչի հետ հեչ էլ սխալ չեմ աշխատում` դասական աշխատելու ձևն է: Ինչ կապ ունի, թե ինչ թիվա? փոփոխական է, կարևորը որ հետո արժեք տաս: Մի քանի գրառում առաջ Դեյտելի գրքից նույնիսկ մեջբերում եմ արել դրա հետ կապված
    Հեչ իմաստ չեմ տեսնում 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
    Լոխ մունք ենք, մնացածը` լոխ են...

  9. #7
    Լիարժեք անդամ MSGM-ի ավատար
    Գրանցման ամսաթիվ
    02.09.2008
    Գրառումներ
    131
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Եղբայր էդ ինչ թիվա, որ 64 բիտանոց long-ը չի հերիքի? 2-ի 63 Աստիճանից մեծ` 8x10246? էսի քո ասած 1012-ից հաստատ մեծ թիվ ա:
    N=360-ի համար, պատասխանը (այսինքն` 360-րդ տարում ապրողների քանակը) 8,508,275,536,357,516,150 ա: N=370-ի պատասխանը long long-ում տեղ չի անում: Էտքան հիշողություն էլ, բնականաբար, չկա:
    Ցուցիչի հետ հեչ էլ սխալ չեմ աշխատում` դասական աշխատելու ձևն է: Ինչ կապ ունի, թե ինչ թիվա? փոփոխական է, կարևորը որ հետո արժեք տաս: Մի քանի գրառում առաջ Դեյտելի գրքից նույնիսկ մեջբերում եմ արել դրա հետ կապված
    Հեչ իմաստ չեմ տեսնում vector օբյեկտից օգտվելու մեջ` ցուցիչը լիովին բավարար է:
    Ո՞նց սխալ չես աշխատում, եթե իմ մոտ runtime error ա տալիս քո կոդը: Ասում եմ` քո ցուցիչ-փոփոխականին նույնիսկ արժեք չես տալիս, գոնե գրեիր.
    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;
    Dictionary-ն էլ հեչ էլ map-ը չի:
    Dictionary-ն Microsoft Scripting Runtime գրադարանի օբյեկտ է` որ լեզուն հնարավորութուն ունի այդ գրադարանին դիմելու` կարող ես հայտարարել:
    Կառուցվածքն էլ հետևյալն է.
    D (key, value) ու value-ն կարող են լինել ցանկացած տիպի, նույնիսկ այլ օբյեկտ:
    Ես ի նկատի չունեի, որ std::map-ը Microsoft Scripting Runtime-ի Dictionary ա, այլ որ std::map-ը dictionary տեսակի data structure ա, էլի ունի map<key, value> տեսքը ցանկացած տիպի key-ի ու value-ի համար (պայմանով, որ key-ի վրա համեմատության օպերատոր կա սահմանած):
    Չեմ կարծում, որ մատրիցաների բազմապատկումը մեծ թվերի պարագայում կարող է այդքան արագ լինել` 900 անգամ:
    KxK չափի երկու մատրիցների բազմապատկումը տրիվիալ ալգորիթմով O(K^3) ժամանակային բարդություն ունի: Մեր խնդրում K-ն կոնստանտ ա (K=35), իսկ հենց "մատրիցի բազմապատկում" գործողությունների քանակը O(logN) ա (N=10^12-ի դեպքում մոտ 40): Այսինքն պետք ա լինում 40 անգամ (35^3)*ինչ-որ-ոչ-շատ-մեծ-կոնստանտ քանակի գործողություններ կատարել, որը հանգիստ կտեղավորվի 0.5 վրկ-ի մեջ: Իսկ եթե ի նկատի ունես կենդանիների քանակը նկարագրող թվերի մեծ լինելը, ապա soultaker-ի առաջարկած խնդրում պետք ա տալ (պատասխան MOD 1000003), ինչը նշանակում ա, որ բոլոր միջանկյալ բազմապատկումներից ու գումարումներից հետո կարելի ա MOD 1000003 անել ու չանհանգստանալ մեծ թվերի մասին:

  10. Գրառմանը 1 հոգի շնորհակալություն է հայտնել.

    Varzor (10.04.2012)

Թեմայի մասին

Այս թեման նայող անդամներ

Այս պահին թեմայում են 4 հոգի. (0 անդամ և 4 հյուր)

Էջանիշներ

Էջանիշներ

Ձեր իրավունքները բաժնում

  • Դուք չեք կարող նոր թեմաներ ստեղծել
  • Դուք չեք կարող պատասխանել
  • Դուք չեք կարող կցորդներ տեղադրել
  • Դուք չեք կարող խմբագրել ձեր գրառումները
  •