C++

[MSGM]

Սպոյլերի մեջ եմ գրում, որ ուրիշներն էլ մտածեն:

 •

• 

 Սեղմել՝ ցույց տալու համար

Նշանակենք F(i,j)-ով i-րդ տարվա վերջում j տարեկան կենդանիների քանակը: Ունենք` F(0,15)=1: Հիմա, ենթադրելով, որ կենդանիները ծնվում և մահանում են տարվա սկզբում,
ծնվածների քանակը (որոնք i-րդ տարվա վերջում դարձած են լինում 1 տարեկան).
F(i,1) = F(i-1,15) + F(i-1,16) + ... + F(i-1,34) (անցած տարվա վերջում 35 տարեկան եղածները մահացել են ու սերունդ այս տարի չեն տալիս)
մյուսների քանակները.
F(i,j) = F(i-1,j-1) (j = 2..35)
N-րդ տարվա վերջում էլ
Պատասխան = F(N,1) + F(N,2) + ... + F(N,35)

#include <iostream>

using namespace std;

int F[2000][40], N;

int main()
{
	cin >> N;
	F[0][15] = 1;
	for (int i = 1; i <= N; i++)
	{
		int s = 0;
		for (int j = 15; j < 35; j++)
			s += F[i - 1][j];
		F[i][1] = s;
		for (int j = 2; j <= 35; j++)
			F[i][j] = F[i - 1][j - 1];
	}
	int ans = 0;
	for (int i = 1; i <= 35; i++)
		ans += F[N][i];
	cout << ans << endl;
	return 0;
}

[Hermsbir]

Խնդրի լուծման ալգորիթմը ճիշտ է, բայց դե, 500 տարի հետո քանի՞ հատ կլինի

[Lusina]

Ժող,մի հատ սենց հարց.Ի՞նչ ա նշանակում հղում հղման վրա. c++ -ի ստանդարտն ասում ա, որ չի թույլատրվում, ու տրամաբանական էլ ա, որովհետև հղումը օբյեկտի վրա պետք ա լինի, իսկ ինքը հղումը օբյեկտ չի,ուղղակի լրացուցիչ անուն ա օբյեկտի համար.Հիմա հարցն էն ա, թե որ դեպքերում ա հնարավոր ունենալ T&& տիպ, որովհետև boosti-i remove_reference-ի մեջ էդ տարբերակն էլ ա հաշվի առած.

[soultaker]

Ո՞վ կարող է լուծել հետևյալ խնդիրը:

Տրված է 1 հատ 15 տարեկան կենդանի: Այդ կենդանին այնպիսին է,որ ապրում է 35 տարի, իսկ սեռահասունացումը տեղի է ունենում 15 տարեկանում: Սկսած 15 տարեկանից կենդանին ամեն տարի ունենում է 1 ձագ : Բազմանալու համար կենդանուն զույգ չի պահանջվում: Գրել ծրագիր, որը պահանջի տարիների քանակ և դուրս բերի, թե այդքան տարի հետո քանի կենդանի կլինի: Ծրագիրը պետք է աշխատի մեծ թվերի համար (~800-1000 տարի):

Կառաջարկեմ նույն խնդիրը, երբ տարիների քանակը կարող է լինել մինչև 1 000 000 000, իսկ պատասխանի փոխարեն պետք է տպել քանակը 1 000 003 -ի վրա բաժանվելուց ստացվող մնացորդը (մեծ թվերից խուսափելու համար):

[Hermsbir]

Խնդրի բարդություններից մեկը հենց մեծ թվերն են -_-

[soultaker]

Խնդրի բարդություններից մեկը հենց մեծ թվերն են -_-

Դե նշված 800-1000 քանակի դեպքում ուղղակի պիտի որ կենդանիների քանակը մեծ ստացվի, որը պահելու համար պետք կգա գրել երկար թվաբանություն ձեռքով, իսկ իմ առաջարկած պայմանների դեպքում բարդությունը կայանում է նրանում, որ հնարավոր չի լինում խնդիրը լուծել տրիվիալ տարբերակով` այսինքն ուղղակի հերթով դիտարկելով քանակները ըստ ամեն տարվա:

[Hermsbir]

Ձեր առաջարկածը ուղղակի մաշտաբավորման խնդիր չէ?

[soultaker]

Ձեր առաջարկածը ուղղակի մաշտաբավորման խնդիր չէ?

Մասշտաբավորում ասելով կոնկրետ ի՞նչը նկատի ունես: Ճիշտն ասած ծանոթ չեմ այդ տերմինին, իմ առաջարկած սահմանափակումների նպատակը խնդրի ալգորիթմական բարդությունը մեծացնելն էր, որ տրիվիալ ալգորիթմը դանդաղ աշխատի ու ցանկալի լինի ուրիշ արագ լուծում:

[Hermsbir]

Դիցուք ծնվողների քանակը 1 000 004 է : Այդ թվից ուղղակի կհանենք 1 000 003, որովհետեև այդքան հատը վերջնական պատասխանում ներդրում չեն ունենա: Էսքան բան չի?

[MSGM]

Կառաջարկեմ նույն խնդիրը, երբ տարիների քանակը կարող է լինել մինչև 1 000 000 000, իսկ պատասխանի փոխարեն պետք է տպել քանակը 1 000 003 -ի վրա բաժանվելուց ստացվող մնացորդը (մեծ թվերից խուսափելու համար):

Երկար հանրահաշիվ գրելու հավես չկա, բայց դրա վրա մտածել կարելի ա: Իմ գրած լուծումը փաստորեն 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-ի համար:

[soultaker]

Երկար հանրահաշիվ գրելու հավես չկա, բայց դրա վրա մտածել կարելի ա: Իմ գրած լուծումը փաստորեն 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-ը տարիներ քանակն է):

[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 աստիճան բարձրացնենք:

[soultaker]

Եթե վերաձևակերպեմ լուծումը, 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 աստիճան բարձրացնենք:

Հենց դա էլ նկատի ունեի:

[Varzor]

Ժողովուրդ ինչի եք բարդացնում?
Բավարար է, որ պահեք մի հատ միաչափ զանգված, էլէմենտների քանակը նախապես չսահմանած` ցուցիչով, որտեղ ամեն էլէմենտի արժեքը կլինի տվյալ կենթադու տարիքը:
Հետո ըստ տարիների ցիկլով անցնում ենք էդ զանգվածի վրայով:
Եթե կենդանի սեռահասուն է (15<=k<=35), ապա զանգվ ածում մեկ տարր ավելացնում ենք ու իրա տարիքը դնում 1, քանակը մի հատով ավելացնում:
Եթե կենդանին 35 է, ուրեն տարիքը դնում ենք զրո` սատկել է ու քանակը մի հատ հանում:
Ցանկացած տարիների համար էլ աշխատում է` տրիվյալ լուծում է, բայց կարծում եմ կարելի է օպտիմիզացնել

 •

• 

 Սեղմել՝ ցույց տալու համար

#include <iostream>
using namespace std;
void main()
{
	int tari, qanak, n, i, j;
	int *k;
	cout<<"tari=";
	do
	{cin>>tari;}
	while(tari<=0);
	k[0]=15;
	qanak=1;
	n=1;
	
	for (i=0; i<tari; i++)
	{
		for (j=0; j<n; j++)
		{
			if (k[j]>0) //yete satkac che
			{
				if (k[j]<=35 && k[j]>=15) //yete der serahasun e
				{
					n=n+1;
					k[n]=1;
					qanak=qanak+1;
				}
				if (k[j]=35) // yete satkelu vra e :D
				{
					k[j]=0;
					qanak=qanak-1;
				}
				k[j]=k[j]+1; //mek tarov mecacav
			}
		}
	}
	cout<<"qanak="<<qanak<<endl;
}

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

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

[MSGM]

Զանգվածի մեծությունը փաստորեն տվյալ տարվա դրությամբ երբևիցե ապրած կենդանիների քանակն ա, չէ? Բայց մի քանի 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;