Создание программы деления без использования деления в Python - PullRequest
Новая
       20

Создание программы деления без использования деления в Python

0 голосов
/ 08 марта 2019

Я работал над этой проблемой на хакерранке

С учетом числителя и делителя целых чисел без знака выведите частное и остаток.Вы не можете использовать деление, не можете использовать мод, и вы хотите оптимизировать для скорости

Моя первоначальная идея была (в Python) 

def divide_problem(num, div):
    quotient = 1
    while (div * quotient) < num:
        quotient += 1
    remainder = (div*quotient) - num

    print(quotient, "quotient")
    print(remainder, 'remainder')


print(divide_problem(31, 5))

Но с этим подходом я получаю7 как частное и 4 как остаток.Мне удалось найти правильное решение онлайн: 

def divide_problem(num, div):
    quotient = 1
    while num - (quotient * div) >= div:
        print(num - (quotient * div), "loop")
        quotient += 1
    remainder = num - (quotient * div)

    print(quotient, "quotient")
    print(remainder, 'remainder')


print(divide_problem(31, 5))

Я не смог выяснить условное утверждение для цикла while 

while num - (quotient * div) >= div:

Что бы вы думалипроцесс, чтобы придумать это заявление?

Ответы [ 3 ]

1 голос
/ 08 марта 2019

num - (quotient*div) >= div математически совпадает с ((quotient+1) * div) <= num

Это почти та же идея, что и у вас, но вы ошиблись. Когда я работаю над такими вещами, я всегда проверяю граничные условия.

Ваше состояние говорит: "Коэффициент слишком мал, если quotient*div < num". Так что попробуйте в некоторых случаях quotient*div == num-1 и убедитесь, что коэффициент действительно слишком мал. И попробуйте несколько случаев, когда quotient*div == num и убедитесь, что коэффициент действительно достаточно велик.

Теперь здесь также есть уровень 2, о котором вам не нужно беспокоиться. Точная форма, используемая во втором цикле - num - (quotient*div) >= div - тщательно написана, чтобы не создавать промежуточных результатов, которые больше, чем num и div. Это гарантирует, что вы получите правильные ответы, даже если вы используете максимально большие целые числа для num и / или div.

Если вы напишите его как ((quotient+1) * div) <= num, тогда (quotient+1)*div может оказаться слишком большим, чтобы представлять его как целое число, что может привести к неправильному ответу условия (во многих языках и, по крайней мере, в некоторых версиях питон IIRC).

1 голос
/ 08 марта 2019

Это просто потому, что remainder НЕ может быть больше, чем divider.

И num - (quotient * div) дает ровно remainder.

Так что если num - (quotient * div) эточем больше divider, это означает, что quotient является недостаточно большим .

Вот почему необходимо продолжать делать это до тех пор, пока remainder не станет меньше divider.

0 голосов
/ 24 июня 2019

Официальное решение - просто неэффективная реализация повторного вычитания, которая заменяет простое вычитание более сложным умножением; если вы собираетесь использовать повторное вычитание, вы должны хотя бы избавиться от умножения: 

def divide(num, div):
    quot = 0
    while div <= num:
        quot += 1
        num -= div
    return quot, num

Повторное вычитание не «оптимизировано для скорости», как вы увидите, если позвоните divide(1000000000,3). Вместо этого мы могли бы использовать повторное вычитание квадратов делителя, или квадратов квадратов делителя, или ..., продолжая до тех пор, пока квадрат квадрата ... делителя не превысит число. В качестве примера рассмотрим проблему divide(1000000000,3), упомянутую выше. Сначала мы составим список квадратов: 

3 * 3 = 9
9 * 9 = 81
81 * 81 = 6561
6561 * 6561 = 43046721

Мы останавливаемся там, потому что следующий квадрат превышает цель. Теперь мы вызываем наивный алгоритм деления на повторные вычитания повторно для каждого остатка: 

divide(1000000000, 43046721) = (23, 9925417)
divide(9925417, 6561) = (1512, 5185)
divide(5185, 81) = (64, 1)
divide(1, 9) = (0, 1)
divide(1, 3) = (0, 1)

Последний остаток равен 1. Коэффициент: 

0*3/3 + 0*9/3 + 64*81/3 + 1512*6561/3 + 23*43046721/3 = 333333333

и мы выполнили только 23 + 1512 + 64 = 1599 вычитаний вместо 333 333 333 вычитаний официального решения. Вот код: 

def divide(num, div):
    divs, sqs, sum = [div], [1], 0
    while divs[-1] * divs[-1] < num:
        divs.append(divs[-1] * divs[-1])
        sqs.append(sqs[-1] * sqs[-1] * div)
    while divs:
        div, sq = divs.pop(), sqs.pop()
        quot = 0
        while div <= num:
            quot += 1
            num -= div
        sum += (quot * sq)
    return sum, num

Первый while вычисляет и суммирует квадраты, а также каждый из квадратов, разделенных на div , поэтому в конечном коде деления нет. После первых while стеки divs и sqs выглядят так: 

divs = [3, 9, 81, 6561, 43046721]
sqs  = [1, 3, 27, 2187, 14348907]

Второй while многократно извлекает два стека, выполняет наивный алгоритм деления на повторные вычитания в третьем while и накапливает сумму . Это намного быстрее, чем официальное решение, и не намного сложнее.

Вы можете запустить программу на https://ideone.com/CgVT1i.

...