Написание рекурсивной функции для умножения 2 целых чисел с поворотом

Question

Это мое домашнее задание. Также может показаться, что на этом форуме люди обращаются за помощью по аналогичным функциям, но я не могу найти что-то достаточно подходящее для меня.

Вот;

Nat multiply(Nat a, Nat b) функция принимает до 2 значений типа Nat. Они содержат int theValue значение и bool isValid значение. Второе в основном не имеет значения (насколько я понимаю.)

Я пытаюсь умножить эти два значения Nat. Это то, что я имею в настоящее время, хотя оно часто меняется, так как я все больше и больше разочаровываюсь в этом; [РЕДАКТИРОВАТЬ] -> вот немного пересмотренное издание;

    if(b.theValue == 1){
    return a;
}
else if(a.theValue == 0 || b.theValue == 0){
    a.theValue = 0;
    return a;
}
else{
    a = add(a, a);
    b = decrement(b);
    return multiply(a, b);
}

[EDIT] это работает для значений 1 и нуля. Я собираюсь реализовать ваши полезные советы.

Ограничения заключаются в том, что я не могу напрямую использовать оператор "+" или оператор "*", и он должен быть рекурсивным. Я могу однако использовать increment а также decrement функция, которая принимает один аргумент Nat и увеличивает его на один. Я также могу использовать add а также subtract Функция, которую я написал сам и тщательно протестировал.

В основном мне кажется, что у меня проблемы с пониманием того, как я могу изменить эти значения, не влияя на то, сколько раз изменяется другое. то есть; Как можно достичь базового случая при добавлении того же значения для b к a? Я как бы понимаю концепцию рекурсии, но эта проблема беспокоит меня.

Как вы, наверное, видите, я не уверен, что делаю. Ответы, которые дает мне эта функция, ОТКЛЮЧЕНЫ.

Любая помощь приветствуется, и спасибо заранее.

[EDIT] Это помогает, и я все ближе, ха-ха, спасибо.

[ПРАВКА] Я попросил учителя помочь, и он указал на кажущееся очевидным решение. Здесь это без изменения заголовка в случае, если другие будут искать;

    if(b.theValue == 1){
    return a;
}
else if(a.theValue == 0 || b.theValue == 0){
    a.theValue = 0;
    return a;
}
else{

    //a = add(a, a);
    b = decrement(b);

    return add(a , multiply(a, b));
}

Я пропускал какой-то фундаментальный мыслительный процесс, связанный с рекурсией. Это имеет смысл для меня сейчас, хотя. Еще раз спасибо, ребята.

Answer 1

Вы должны пройти через это вручную с простым умножением, таким как 2*1... вы, вероятно, увидите, что проблема в a = add(a, b);, a*b является a+a+a+a+… пока у вас нет b общие условия a, Ваша рутина добавляет b когда это должно только уменьшаться b (который фактически является счетчиком сложения).

Чтобы установить это как рекурсивную подпрограмму, вам на самом деле понадобится третий параметр... что-то для хранения добавляемого значения, так что вы можете a = add(a, original_a); - original_a не должны быть изменены в течение всей операции.

Nat multiply(Nat a, Nat b)
{
    if (a.theValue == 0) return a;
    if (b.theValue == 0) return b;
    return recursive_multiply(a, b, a);
}

Nat recursive_multiply(Nat a, Nat b, Nat adder)
{
    if (b.theValue == 0) return a;
    a = add(a, adder);
    b = decrement(b);
    return recursive_multiply(a, b, adder);
}

Answer 2

Я думаю, что я в том же классе, что и вы, и если так, у меня есть кое-что действительно важное для упоминания, которое существенно изменит весь ваш ответ. В функции упоминается это:

// вы не можете получить доступ к полям в Натс напрямую

Это означает, что вы не можете использовать a.theValue или b.theValue вообще в этом вопросе. Если вы это сделаете, вы получите 0 баллов за эту функцию. Чтобы подтвердить, что у вас есть мое назначение, у вас случайно есть функция с именем bool zero (Nat n)? Если это так, вы должны использовать эти функции, как и другие функции, такие как увеличение, уменьшение и NotANat.

Это функции, которые вы должны использовать для сложения, умножения и вычитания:

// given an integer, create a Nat
// This is the only way you should create Nats!
bool NotANat(Nat n)
{
    return !(n.isValid);
}

// given a Nat, check if it is zero or not
bool zero(Nat n)
{
    if (n.isValid) {
        return n.theValue == 0;
    }
    else
    {
        return false;
    }
}

// given a Nat, returns a Nat one less
// Note: we cannot allow this function to produce a negative value
// so to avoid that, we'll set the invalid flag

Nat decrement(Nat n)
{
    if (n.isValid && n.theValue > 0)
    {
        n.theValue = n.theValue - 1;
    }
    else
    {
        n.isValid = false;
    }
    return n;
}

// given a Nat, returns a Nat one greater
Nat increment(Nat n)
{
    if (n.isValid) {
        n.theValue = n.theValue + 1;
    }
    return n;
}

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

РЕДАКТИРОВАТЬ: Поскольку задание выполнено, я могу дать ответ сейчас. Вот что у меня было для моего задания, и я несколько раз тестировал его, и оно работает:

// ToDo: add()
//       given 2 Nats a,b, return a Nat that represents the sum a+b
//       you may not use + directly
//       you may not access the fields in the Nats directly
//       you must use recursion!
//       you may use any functions already defined for Nat

Nat add(Nat a, Nat b)
{
    if (zero(b)){
        return a;
    } else {
            return add(increment(a), decrement(b));
    }
}


// ToDo: multiply()
//       given 2 Nats a,b, return a Nat that represents the product a*b
//       you may not use * or + directly
//       you may not access the fields in the Nats directly
//       you must use recursion!
//       you may use any functions already defined for Nat
//       Hint: you should use add()

Nat multiply(Nat a, Nat b)
{
    if(zero (b)){
        return b;
    } else {
        return add(a, multiply(a, decrement(b)));
    }
}


// ToDo: subtract()
//       given 2 Nats a,b, return a Nat that represents the difference a-b
//       you may not use - directly
//       you may not access the fields in the Nats directly
//       you must use recursion!
//       you may use any functions already defined for Nat

Nat subtract(Nat a, Nat b)
{
    if (zero(b)){
       if(NotANat(a){
          return a;
       }else{
          return a;
       }
    } else {
        return subtract(decrement(a), decrement(b));
    }
}

Поэтому в основном я использую "bool zero(nat n)" в качестве базового оператора для всех трех функций, потому что это единственная примитивная функция, которую пользователь может использовать без прямого доступа к полям вашей функции. Мы возвращаем b в функции умножения, потому что когда b равно нулю, он вернет 0, поэтому функция выполняется. В вашем примере упоминается, что если b равен единице, он вернет a в качестве базового варианта. В большинстве случаев это обычный способ ответить на него, но, как я уже говорил, вы не можете использовать поля, которые означают, что функция будет помечена как ноль. Поэтому это один из способов сделать ответ. Весь смысл этого задания не в умножении с использованием функции, а в том, чтобы использовать свои знания, чтобы заставить примитивные функции работать и правильно использовать рекурсию. Я, возможно, объясняю это неправильно, так как это мой первый год в этом, но если кто-то хотел бы расширить это, это было бы очень признательно.