Loading...
enevlogiev avatar enevlogiev 1168 Точки

[Challenge] Числото Х на степен N

Естествено, ще е хубаво да не използвате Math.Pow() : ))
За да е по-интересна задачата, нека има две подусловия.

1) Имате право да ползвате цикли, но нямате право да ползвате умножение.

2) (за малко по-напреднали) Имате право да използвате умножение, но нямате право на цикли.

Има отговори в гугъл, ще се радвам, ако първо помислите сами. Авторски решения засега няма : )

 

Edit: (tnx Фил Колев) Достатъчно е програмата да работи с цели положителни числа. Може да ползвате BigInteger, ако искате. Ако някой измисли вариант за реални числа или отрицателни степени, нека го предложи : )

Тагове:
8
Programming Basics 09/04/2015 02:07:51
mihayloff14 avatar mihayloff14 824 Точки

а за проблем 2 може ли да ползваме рекурсия ? :D

1
enevlogiev avatar enevlogiev 1168 Точки

Ами разбира се : ) Аз се опитвам да измисля рекурсивно със събиране само, обаче в главата ми се въртят едни варианти, при които при 2^16 примерно, в стака ще има към 2^16 call-a .. aко не се строши много преди това.

0
angeldown avatar angeldown 7 Точки

Защо да ползвам рекурсия, като мога да ползвам итерация?

0
enevlogiev avatar enevlogiev 1168 Точки

Според второто условия нямаш право на итерация

0
Filkolev avatar Filkolev 4482 Точки

А с какви числа работим? Ако степента е реално число става забавно :D Ако е отрицателна пак е по-собен случай.

1
enevlogiev avatar enevlogiev 1168 Точки

Хм, трябваше да го съобразя. С естествени засега.

0
RoYaL avatar RoYaL Trainer 6849 Точки

За отрицателните степени може да се ползва tail recursion. Но все още си мисля, че има начин да се намери резултата с побитови операции :D

0
Filkolev avatar Filkolev 4482 Точки

Ако може да ползваме деление отрицателната степен е лесна: намираме резултата от повдигане на степен на абсолютната стойност и делим 1 на резултата. 5^-3 == 1/(5^3).

0
RoYaL avatar RoYaL Trainer 6849 Точки

Тук ще трябва да се намеси BigInt.

Иначе не се сетих за начин да компютна степепна само с умножение, деление и т.н. Сигурно има някакъв побитов начин, ама не ми е минал през акъла все още.

Щом може с рекурсия обаче няма ядове :D

Ето ги моите решения:

static void Main()
    {
        int num = 88;
        int pow = 10;


        // with loops
        decimal res = num;
        decimal inc = num;

        for (int i = 1; i < pow; i++)
        {
            for (int j = 1; j < num; j++)
            {
                res += inc;
            }
            inc = res;
        }

        Console.WriteLine(inc);

        // ---------------------------------------

        // without loops (recursion)
        Console.WriteLine(Pow(num, pow));
    }

    static decimal Pow(int num, int pow, decimal result = 1)
    {
        if (pow == 0) return result;
        result *= num;
        pow--;
        return Pow(num, pow, result);
    }
0
quickben avatar quickben 966 Точки

12-те реда правилото ванка :)

0
10/04/2015 02:06:00
Filkolev avatar Filkolev 4482 Точки

Доста тъпи грешки направих в процеса на решаване, но по това време е нормално. Все пак мисля, че успях да си изчистя бъговете. Ето решенията:

Условие 1

Условие 2

1
mihayloff14 avatar mihayloff14 824 Точки

Първия проблем да се намери числото само със събиране става лесно. Ето решение:

Solution 1

Ако степента е отрицателна, подходът е същия, но накрая печатаме 1/x, а не x;

Решение за второто условие (не можах да се сетя как ще стане без глобална/статична променлива):

// TODO

PS: Пиша на JS, защото не ми се чака Visual studio да зареди.

0
09/04/2015 15:22:03
RoYaL avatar RoYaL Trainer 6849 Точки

Ъъъъ.. Пробвал ли си примерно с 6 на 3та?

0
mihayloff14 avatar mihayloff14 824 Точки

Явно от бързане подцених задачата и забравих да проверя други варианти. :/

0
enevlogiev avatar enevlogiev 1168 Точки

Това е моят вариант 2.

Щеше ми се да заинтригувам някой от ниво 0. Поне да пробва итеративното решение.

1
taylorswift avatar taylorswift 54 Точки

if (y == 1)

{

    return x;

 

ти е излишно

0
enevlogiev avatar enevlogiev 1168 Точки

Знам, реално при числа по-големи от 1 имам един метод по-малко в стака. Не е кой знае к'ва оптимизация. Оставих го, защото това ми беше оригиналното дъно, (y == 0) го добавих по-късно, защото се сетих, че и нулата е валидна степен.

1
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Оригинално решение!

0
GerasimVelchev avatar GerasimVelchev 1 Точки

А след като прочетете за Exponentiation by squaring, можете значително да ускорите алгоритъма си за задача 2.

0
09/04/2015 13:51:40
RoYaL avatar RoYaL Trainer 6849 Точки

Понеже винаги си правя рекурсиите да не мутират входните данни, а да използват отделни данни, като в по-горния пример с result-a, се забутах в много голям филм с тоя алгоритъм, докато се усетя, че входните ми данни трябва да са BigInt и те, иначе докато ги мутира ще прехвърли int-а :)

Иначе оптимизира с доста, наистина. А така май е още по-оптимизирано:

http://codereview.stackexchange.com/questions/21169/how-to-improve-this-functional-python-fast-exponentiation-routine

 

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.