Бройни системи

[Гост]

Здравейте! Имам нужда от помощ с тази задача. Не ми е ясно как става решението, затова ако може някой да ми обясни с една от подточките, а аз да се опитвам с останалите.

Направете съответствие между n-бройна система (с основа n) и запишете десетичното число 2014 чрез нея.
А) n=3
Б) n=6
В) n=4

Благодаря!!!

[peyo]

Здравейте! Имам нужда от помощ с тази задача. Не ми е ясно как става решението, затова ако може някой да ми обясни с една от подточките, а аз да се опитвам с останалите.

Направете съответствие между n-бройна система (с основа n) и запишете десетичното число 2014 чрез нея.
А) n=3
Б) n=6
В) n=4

Благодаря!!!

Не знам какво значи "Направете съответствие между n-бройна система (с основа n)". Вместо това да видим дали можем да превърнем десетичното число 2014 в троично.

$2014 = 2*10^3 + 0*10^2 + 1*10^1 + 4*10^0$

И сега ще търсим $x_i$-тата където всяко $x_i$ e от 0 до 2 включително [0,2]:

$2014 = ... \ x_3*3^3 + x_2*3^2 + x_1*3^1 + x_0*3^0 $

Може би има няккава формула или фокус, с който можем да превръщаме числа от една вв друга бройна система, но ние не я знаем, затова да пробваме да измислим начин.

Степените на 3-ката са:

Код: Избери целия код

0 1 2 3  4  5   6    7
1 3 9 27 81 243 729  2187

Явно няма да ни трябва 7, защото е над 2014. Значи да започнем от 6:

$2*729 = 1458$

По малко е затова го запазваме и така имаме $x_6 = 2$:

$2014 = 2*3^6 + x_5*3^5 + ...= 1458 + x_5*3^5 ...$

Да видим далли $x_5 e 2$:

$1458 + 2*243 = 1944$

По малко е от 2014, затова може да е 2 и така $x_5 = 2$:

$2014 = 2*3^6 + 2*3^5 + x_4*3^4...= 1944+ x_4*3^4 ...$

Да видим дали $x_4 може да е 2$:

$1944+ 2*81 = 2106$

Не може, да видим 1:

$1944+ 1*81 = 2025$

Не може значи е 0:

$2014 = 2*3^6 + 2*3^5 + 0*3^4 + x_3*3^3 ...= 1944+ x_3*3^3 ...$

Да видим дали $x_3 може да е 2$:

$1944+ 2*27= 1998$

Може, значи е 2:

$2014 = 2*3^6 + 2*3^5 + 0*3^4 + 2*3^3 + x_2*3^2 ...= 1998+ x_2*3^2 ...$

Да видим дали $x_2 може да е 2$:

$1998+ 2*9= 2016$

Не може, 1:

$1998+ 1*9= 2007$

Може, значи е 1:

$2014 = 2*3^6 + 2*3^5 + 0*3^4 + 2*3^3 + 1*3^2 + x_1*3^1 ...= 2007 + x_1*3^1 ...$

Да видим дали $x_1 може да е 2$:

$2007 + 2*3= 2013$

Може, значи е 2:

$2014 = 2*3^6 + 2*3^5 + 0*3^4 + 2*3^3 + 1*3^2 + 2*3^1 + x_0*3^0 ...= 2013 + x_0*3^0 ...$

И сега от 2013 до 2014 ни трябва само една 1-ца, значи $x_0=1$:

$2014 = 2*3^6 + 2*3^5 + 0*3^4 + 2*3^3 + 1*3^2 + 2*3^1 +1*3^0 = 2013 + 1 = 2014$

И така в троична бройна система 2014 трябва да е:
2202121

Дали това е добър метод/ алгоритъм за решаване на такъв вид задачи? Нямам представа. Но ми се струва, че е лесно да се напише програма която да го прави. Да се опитаме да изчислим $O()$ на този алгоритъм като знаем N = 2014.

Първо намираме най-голямата степен от която да тругнем за константно време $log_3 2014 = 6.924989053692301 - >7$

Сега въртим цъкъл по всяко от тези 7, знаи дотук имаме $O(log_3 N)$

Въвъ всеки цикъл правим най-много 3 изчисления, значи $O(3*log_3 N)$

С което в крайна сметка намерихме $O(log \ N)$. Това мо изглежда съвсем добър алгоритъм от практична гледна точка. По добър би бил $О(log \ log \ N)$ или $O(1)$ например, но не зная дали има такъв. Ако някой знае повече моля да пише.