Как сделать деление без "/"? - PullRequest
Новая
       13

Как сделать деление без "/"?

0 голосов
/ 26 января 2019

ПРОБЛЕМА 2: Рассмотрим конечное множество S с n элементами;число различных подмножеств S с ровно двумя называется «n выбирать 2» и обычно записывается как n / 2.Вы можете вспомнить, что n / 2 = (n (n-1)) / 2.

Ниже приведена (тривиальная) функция C ++, которая принимает неотрицательное целое число n и возвращает n / 2 (также не-отрицательное целое число): 

unsigned int n_choose_2(unsigned int n) {
    if(n==0) 
       return 0;
    else 
       return n*(n-1)/2;
 }

Ваша работа: написать функцию, которая также возвращает n / 2, но со следующими ограничениями:

  • Вы не можете использовать оператор умножения *
  • Вы не можете использовать оператор деления /
  • У вас не может быть циклов
  • Вы не можете добавлять какие-либо дополнительные параметры к функции
  • Ваша функция должнабыть самодостаточным: никаких вспомогательных функций!
  • Нельзя использовать глобальные переменные
  • Нельзя использовать статические переменные
  • Нельзя использовать какие-либо операции с «битым твидлингом» - нетсдвиги и т. д.

Однако:

  • Вы можете использовать рекурсию
  • Вы можете использовать операторы + и -.

Это то, что я получил, нужна помощь, чтобы не использовать / и проверить, правильно ли я. 

unsigned int n_choose_2(unsigned int n) {
    if(n==0) 
         return 0;
    else 
         return n_choose_2(n)/2 - n/2;
}

1 Ответ

0 голосов
/ 26 января 2019

Вот все подсказки, которые вам нужны.Вы пытаетесь вычислить (n*(n-1))/2

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

for (int n = 0; n < 20; n++)
{
    std::cout << "n_choose_2(" << n << "):  " << (n * (n-1)) / 2 << std::endl;
}

Конечно, выне может представить это, потому что он использует запрещенную математическую операцию.Но давайте посмотрим, что он печатает: 

n_choose_2(0):  0
n_choose_2(1):  0
n_choose_2(2):  1
n_choose_2(3):  3
n_choose_2(4):  6
n_choose_2(5):  10
n_choose_2(6):  15
n_choose_2(7):  21
n_choose_2(8):  28
n_choose_2(9):  36
n_choose_2(10):  45
n_choose_2(11):  55
n_choose_2(12):  66
n_choose_2(13):  78
n_choose_2(14):  91
n_choose_2(15):  105
n_choose_2(16):  120
n_choose_2(17):  136
n_choose_2(18):  153
n_choose_2(19):  171

Теперь посмотрим, на какую величину увеличивается каждая строка.

Возьмите любые две соседние строки (кроме первой пары) и вычтите разницу.Например, n_choose_2(10) - 45, а n_choose_2(9) - 36. n_choose_2(10) - n_choose_2(9) == 9.

n_choose_2(19) - n_choose_2(18) - это то же самое, что и 171 - 153, то есть 18.

Обратите внимание на шаблон?

Вот все, что вам нужно: 

unsigned int n_choose_2(unsigned int n)
{
    if (n <= 1)
    {
        return 0;
    }

    // WHAT COMES NEXT IS UP TO YOU....
}
...