GeOlymp Forum: [გ]ამოცანა კომპლექსურ რიცხვებზე

[გ]ამოცანა კომპლექსურ რიცხვებზე

ავტორი Dixtosa

გამრავლება სამ გამრავლებაში

წერილები: 57

26 მაისი 2012, 21:15

დაწერეთ კოდი ან ფსევდოკოდი ორი კომპლექსური რიცხვის ნამრავლის გამოთვლისა სამი გამრავლების ოპერაციის გამოყენებით. წარმოსახვითი და ნამდვილი ნაწილები ნამდვილი რიცხვებია.

წერილები: 49

scientist1642 says:

27 მაისი 2012, 13:03

$(a + b i) * (c + d i) = ac - bd + i(ad + bc)$

გამოვთვალოთ $ac , bd$ და $(a + b) (c + d)$ (3 გამრავლება)

$ad + bc = (a + b)(c + d) - ac - bd$

წერილები: 48

nikaj says:

28 მაისი 2012, 3:41

სხვათაშორის თითქოს ძალიან მარტივი რაღაცაა მაგრამ ამის გამოყენებით ხდება ორი N ნიშნა დიდი რიცხვის გამრავლება N^2 ზე ბევრად ნაკლებ ოპერაციაში (სწრაფი გამრავლების ერთ-ერთი ალგორითმია). ვინც არ იცით ეს ალგორითმი გირჩევთ იფიქროთ.

მინიშნება: N აიღეთ 2 ის ხარისხი. თუ ზუსტი ხარისხი არაა, რიცხვებს წინ 0 ებს დაუმატებთ რომ შეავსოთ 2 ის ხარისხამდე.

წერილები: 83

tsotne says:

28 მაისი 2012, 11:02

ხო, Divide and Conquer-ით იხსნება თუ სწორად მახსოვს N*sqrt(N) დროში :)

წერილები: 48

nikaj says:

30 მაისი 2012, 2:36

არ არის ეგ N*sqrt(N), N^log2(3) ია.

ბარემ ლინკსაც დავდებ და მერე შეჯიბრებაზე რო მოვა სადმე არ თქვან არ ვიცოდითო :)

კარაცუბა