Возвратите заявление, которое работает, но не имеет особого смысла

Question

У меня есть следующая функция:

int mult(int y, int z)
{
  if (z == 0)
    return 0;
  else if (z % 2 == 1)
    return mult(2 * y, z / 2) + y;
  else 
    return mult(2 * y, z / 2);
}

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

Что меня смущает, так это то, что y отображается только в качестве аргумента и нигде не отображается в возвращении, кроме как в рекурсивной части, и все же функция фактически возвращает y в качестве ответа. *

Как это происходит? Мне нужно уметь следить за всем, что происходит, чтобы я мог выполнить итерации для доказательства.

Answer 1

Поскольку это, очевидно, домашний вопрос, я рекомендую вам сделать то, что задание, скорее всего, предназначало для вас. Проследите через код.

1) дать начальное значение для y и z. 2) на бумаге или в отладчике проследите, что происходит при вызове функции. 3) повторите шаг 2 с текущими значениями y / z до завершения программы.

Answer 2

#include <iostream>

using namespace std;

int mult(int y, int z)
{
  if(z==0) {
    cout<<"z is null! - y:"<<y<<" z: "<<z<<endl;
    return 0;
  }
  else if (z%2==1)
  {
    cout<<"z is odd! - y:"<<y<<" z: "<<z<<endl;
    // make z even 
    return mult(2*y,z/2)+y;
  }
  else 
  {
    cout<<"z is even! - y:"<<y<<" z: "<<z<<endl;
    return mult(2*y,z/2);
  }
}


int main()  {

  cout<<"result: "<<mult(3,13)<<endl;

}

Вывод:

z is odd! - y:3 z: 13
z is even! - y:6 z: 6
z is odd! - y:12 z: 3
z is odd! - y:24 z: 1
z is null! - y:48 z: 0
result: 39

Как это работает для 3 и 13:

Есть переключатель для четных и нечетных чисел (см. Комментарий в коде).

Когда z равно нулю, рекурсия «начинает возвращаться к первоначальному вызову».Если число z нечетное, оно добавляет y к возвращаемому значению рекурсивного вызова, если оно четное, оно возвращает значение рекурсивного вызова.

odd: return 0 + 24
odd: return 24 + 12
even: return 36
odd: return 36 + 3 

Answer 3

Одним из подходов будет перевод каждой строки на «английский». Мой перевод будет примерно таким:

если z равно нулю, вернуть ноль
если z нечетно, вернуть mult (y * 2, z / 2) + y
если z чётно, вернуть mult (y * 2, z / 2)

Общая схема заключается в рекурсивном вызове mult с удвоением первого параметра и уменьшением пополам второго параметра.

Обратите внимание, что здесь вы вызываете mult с z / 2, но его аргументы являются целыми числами, поэтому, если ваша функция продолжает рекурсивно, 2-й параметр будет уменьшаться вдвое каждый раз, пока не опустится до 1, а затем, наконец, 1/2 который округляется до 0 - в этот момент рекурсия остановится, потому что z == 0.

С этими подсказками вы сможете понять, как работает этот алгоритм.

Answer 4

пошаговый анализ

final result: 100
 mult(10, 10)
 {
     makes 100
     mult(20, 5)
     {
         makes 100
         mult(40, 2) + 20
         {
              makes 80
             mult(80, 1)
             {
                   makes 80
                  mult(160, 0) + 80
                  {
                        return 0;
                  }
             }
         }
     }
 }

Answer 5

Примечание. Если это домашнее задание, пометьте его так.

Итак, мы получили три рекурсивных случая. Чтобы все было понятнее, я бы переписал C-код в какой-то функциональный псевдокод. Замените mult на интуитивно понятный знак оператора и найдите описательные объяснения низкоуровневых выражений, таких как (z%2==1).

Вы получите что-то вроде

a ** b = 
| b is 0    -> 0 
| b is even -> 2a ** (b/2) 
| b is odd  -> 2a ** (b/2) + a 

Тебе сейчас понятно?

Answer 6

Не совсем ответ, а скорее предложение.
Вы можете уменьшить рекурсивный вызов с 2 до одного:

int mult(int y, int z)
{
  int result = 0;  
  if (z == 0)
    return result;
  result = mult(2 * y, z / 2);  // Common between "then" and "else"
  if ((z % 2) == 1)
  {
     result += y;
  }
  return result;
}

Это можно упростить еще раз, соблюдая правило "только одна точка выхода":

int mult(int y, int z)
{
  int result = 0;  
  if (z != 0)
  {
    result = mult(2 * y, z / 2);  // Common between "then" and "else"
    if ((z % 2) == 1)
    {
       result += y;
    }
  }
  return result;
}

Хотя многие компиляторы будут выполнять это упрощение автоматически, отладка обычно проще, когда упрощается код. Отладчик будет соответствовать коду при пошаговом выполнении.

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

Answer 7

Демонстрации по индукции основаны на доказательстве того, что результат действителен для первого значения, и что если принцип верен для общего значения N, то доказуемо, что оно справедливо для N+1.

Чтобы упростить, вы можете начать с доказательства того, что он работает для z в { 0, 1, 2 }, что должно быть тривиально с ручным тестом. Затем, чтобы продемонстрировать шаг индукции, вы начинаете с обобщенного z=N и доказываете, что если mult( y, N ) является действительным результатом, то mult( y, N+1 ) также является действительным результатом в терминах предыдущего. Поскольку для четных и нечетных чисел существуют разные ветви, вам придется доказать шаг индукции как для четных, так и для нечетных N чисел.

Answer 8

y a = y a

a = четное число

b = следующее нечетное число (другими словами a + 1)

Таким образом, если вы хотите, чтобы приведенное выше уравнение выражалось только в виде четных чисел («а»), когда им задано нечетное число («б»), вы можете сделать следующее:

y b =y (a + 1) = y * a + y

Теперь запутайте всех, написав 'a' как 2 * (z / 2).

y * a становится (2* y) * (z / 2)

y * b становится ((2 * y) * (z / 2)) + y

, поскольку в формуле для обоихчетные и нечетные числа, мы хотим думать, что код говорит нам, что (2 * y) * (z / 2) = (2 * y) * (z / 2) + y, что, очевидно, безумие!

Причина в том, что мы поняли, что z / 2 является целым числом, поэтому z никогда не может быть нечетным.Компилятор не позволит нам присвоить z / 2 целому числу, если z нечетно.Если мы попытаемся сделать 'z' нечетным, целое число, которое мы на самом деле будем использовать, это (z-1) / 2 вместо z / 2.

Чтобы обойти это, мы должны проверить, чтобы увидеть, является ли z/ 2 нечетно и выбираем нашу формулу на основе этого (например, y a или y b в терминах 'a').

В мульт (y, z) оба 'y'и' z 'оба являются целыми числами.Используя приведенные выше символы, mult (2 * y, b / 2) становится mult (2 * y, a / 2), потому что компилятор урезает b / 2 до a / 2.

Поскольку мы всегдасобираясь получить «a» в качестве параметра для «mult», даже когда мы отправляем «b», мы должны убедиться, что мы используем только формулы, которые требуют «a».Таким образом, вместо y b мы используем y a + 1, как описано выше.

b / 2 = a / 2 + 1/2, но 1/2 не может быть представлено как частьвнутр.