Професионална програма
Loading...
+ Нов въпрос
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

Advanced Loops / Greatest Common Divisor (GCD) / No Euclid Solution

Question

My solution


Някой пробвал ли е да я реши без алгоритъма на Евклид? Решението ми трябва да е правилно, но на последния тест ми дава:

Test #10 (Time limit)

Allowed working time: 0.100 sec

Time used: 0.156 s

Тоест, имам 90%, като последните десет стоят с часовник. Може би трябва да променя условията във for цикъла, за да намаля времето? Какво бихте направили в случая?

Ще ми е интересно да видя и други решения без алгоритъма на Евклид.

0
Programming Basics 29/06/2016 13:54:14
hwfbcisod avatar hwfbcisod 80 Точки
Best Answer

Ползвам твоя метод с малка корекция, колкото да излъжа джъджа:

http://pastebin.com/dR1748QB

1
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

Аха. Намалил си броя цикли, за да съкратиш времето. Това бе и моята идея, но не знам защо се отказах от нея. Браво!

-1
hwfbcisod avatar hwfbcisod 80 Точки

Да, реално така се получава, но само за този случай в джъджа. Оптималното решение ще бъде оригиналното ти решение + постнатото от мен за случаите difference >= smaller и difference < smaller.

1
Plamen27 avatar Plamen27 599 Точки

Здравей,

хитро решение си измислил.

Тъй като последната проверка на която гърмиш по време сравнява 191441250 и 168888720

Най-вероятно тук ти е проблема, както си предположил:

 int smaller = Math.Min(a, b);
        for (int i = oldDivisor; i <= smaller; i++)

На една от предните задачи бях използвал leftshift оператор и по същия начин гърмеше по време на една от проверките.

0
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

Нямам представа, дали е хитро или глупаво. Просто решавах повторно задачите без да гледам подсказките и се оказа, че съм решавал задача за която мислех, че се решава само с Евклид, без Евклид.
Все пак търся решение без Евклид, което да минава на 100%.

0
Perss avatar Perss 7 Точки

Браво, решението ти е много добро! Моята идея беше подобна с разлика, че използвам лист в който складирвам делителите. И от него трябва да принтирам най-големия интиджър. Ето го кода(неработи):

http://pastebin.com/2fmD6Anc

0