Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 24.09.2002, 12:43   #16
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 4
Post

Quote:
Originally posted by Dark Abyss of Yerevan:
Значит так. В цикле крутим числа i от 0 до 27 (9+9+9),
и для каждого i подсчитываем t - число разбиений числа
i ( a+b+c == i/ a,b,c IN [0..9]). Ясно что количество
счастливых билетов с суммой первых (или последних) трех
чисел == i равно t*t (t^2). Там конечно используется оператор
сравнения, но насколько я понял ограничение поставлено для того
чтобы не допустить тупого перебора и сравнения левой части с
правой. Думаю что в данном случае все ок. В крайнем случае
можно изменить процедуру нахождения количества разбиений.

Code:
  #include <stdio.h>


void main(){
int i,i1,i2,i3,t;
long total;

total=0;
for (i=0;i<=27;i++){

	t=0;

	/* найти количество разбиений числа i */
	for (i1=0;(i1<=i)&&(i1<=9);i1++)
		for (i2=0;(i-i1<=18)&&(i1+i2<=i)&&(i2<=9);i2++)
			if (i-i1-i2<=9)t++;

	total+=t*t;
//	printf(&quot;i=%d, t=%d&quot;,i,t);

};

	printf(&quot;\ntotal=%d&quot;,total);




}
Ochen` nedurno, ideya pravil`naya, realizaciyu mozhno poluchshe sdelat`. Esli primenit` massiv, to mozhno povisit` evvektivnost` ~1.5 raza i izbavit`sya ot operatora sravneniya voobshe. V obshem, molodec.
Reply With Quote
Old 24.09.2002, 15:33   #17
Младенец
 
Join Date: 09 2002
Location: ?????????
Posts: 13
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Code:
 Abiss - i lucum@ sxal che, bajc kareli !
 najev ajspes: Vercnenq massiv 3 erkarutjamb(vor@ algoritmi
 ashxatanqi skzbum amboxjovin zro !)
 ev 9 erkarutjamb Numbercount massiv = 0:Im algoritmum ogtagorcvelu !
 nujn algoritm@ inch vor abiss - algoritmum,
 bajc == - @ yndhanrapes chi ogtagorcvelu:Massivi verjin elementin kavelacnenq 1, 
kpahenq @nt acik popoxakan ` count vor@ nujnpes kavelacnenq 1 - ov,
 Numbercount[count - 1]++:Erb vor verjin element@ kdarna 9 ev nran kavelacnenq
 1 apa inchpes sovorakan gumarman
 depqum` naxaverjin element@ kavelana 
1 - ov, isk verjin kzrojacnenq, ajd
 @ntacqum count - @` count - 9 + 1, 
ev Numbercount[count - 1]++: Verjum parzapes`

int total = 0; 
For(int i = 0; i < 9; i++)   
total += (Numbercount[i])^ 2;

total - @ mer patasxann !:&quot;
Reply With Quote
Old 25.09.2002, 12:07   #18
Дошкольник
 
Dark Abyss of Yerevan's Avatar
 
Join Date: 01 2002
Location: hell
Posts: 124
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Ну что же, решите и вы задачку
Дано множество 1,2,..,3n натуральных чисел и какие нибудь 3 непересекающиеся подмножества этого множества по n чисел в каждом. Требуется со всей математической строгостью доказать, что можно
выбрать по одному числу из каждого множества так, чтобы одно число из выбранных равнялась сумме двух других.

P.S.
Я и сам не знаю решения. Задачка эта из учебника 'Тоноян. Комбинаторные Алгоритмы', No4.
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 10:01.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.