Пробегал глазами по рассылке вакансий, попалась интересная задачка:

"В качестве разминки напишите реализацию функции g(n), которая вычисляет n^2, используя из математических операций только + и –.Язык программирования любой, n — натуральное число, вспомогательные переменные использовать не рекомендуется".
На всякий случай, не заморачивайтесь с отрицательными числами.

Но как же без вспомогательных переменных?

Максимум, получилось следующее (но тут они неявно все равно будут в избытке) :
[spoiler]

int G(int n, int itreation = 1)
        {
            if (itreation == n)
                return n;
            return n + G(n, itreation + 1);
        }

[/spoiler]

(n + 1) * (n + 1) = n*n + 2*n + 1 =>

  def g(n: Int): Int = if (n == 0) 0 else g(n - 1) + n + n - 1

Здравствуйте, vsb, Вы писали:

vsb>(n + 1) * (n + 1) = n*n + 2*n + 1 =>

vsb>

vsb>  def g(n: Int): Int = if (n == 0) 0 else g(n - 1) + n + n - 1
vsb>

ты бог! Но как ты до этого додумался?

Здравствуйте, Аноним, Вы писали:

А>как ты до этого додумался?

Предположил, что задачу можно попробовать решить с помощью рекурсии. Для этого надо выразить g(n + x) от предыдущих значений. Раскладываем (n+1)^2 и дальше всё очевидно.

Здравствуйте, vsb, Вы писали:
vsb>Предположил

Выглядело потрясающе, без шуток.
Если это не секрет, как такому можно научиться?
Мне кажется, это истинно математическое мышление.
Возможно ли в нем упражняться, или это преимущественно "от рождения"?

Здравствуйте, Аноним, Вы писали:

А>Пробегал глазами по рассылке вакансий, попалась интересная задачка:

А>"В качестве разминки напишите реализацию функции g(n), которая вычисляет n^2, используя из математических операций только + и –.Язык программирования любой, n — натуральное число, вспомогательные переменные использовать не рекомендуется".
А>На всякий случай, не заморачивайтесь с отрицательными числами.

А>Но как же без вспомогательных переменных?
К.м.к. вопрос на знание техники написания циклов в функциональных ЯП, когда в качестве вспомогательных переменных используешь параметры функции хвостового выхова http://ru.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Реккурентное решение явный оверкилл

Здравствуйте, Аноним, Вы писали:

А>"В качестве разминки напишите реализацию функции g(n), которая вычисляет n^2, используя из математических операций только + и –.Язык программирования любой, n — натуральное число, вспомогательные переменные использовать не рекомендуется".

Достаточно вообще инкремента-декремента... какое там определение функции Аккермана?

А>Но как же без вспомогательных переменных?

Да запросто. Но рекурсия — это нечестно, это те же вспомогательные переменные в неограниченном количестве.
Поэтому делаем так.

n^2 = 1 + 3 + ... + (2k-1) + ... + (2n-1)

int square(int n)
{
  int s = 0; // ну хоть одну переменную нам придётся завести
  // будем крутить цикл назад, от переменной правой границы к константной левой, чтоб правую не хранить и не вычислять
  for(n = n+n-1; n > 0; n = n-2)
    s = s + n;
  return s;
}

У всех оотэнное говно

int64_t mul (int64_t n, int64_t m, int64_t res, int64_t iter)
{
    return 
        (iter==m)        ? res :
        (iter+iter < m)  ?    mul(n, m, res+res, iter+iter) :
        res + mul(n, m-iter, n, 1); 
}

int64_t sqr(int64_t n)
{
    return mul(n, n, n, 1);
}

возведите миллион в квадрат вашим способом и моим

Здравствуйте, Кодт, то, что вы бог кода, я и раньше знал)

Но может быть Вы мне подскажите тогда.
Ведь главное метод и умение его применять в нужной ситуации, не так ли?

Не помню, чтобы в школе и институте учился чему-либо подобному.
Но на практике мне обычно помогало следующее:
1) Взять ручку и бумагу.
2) Записать результаты.
3) Выявить какую-то закономерность.

Простую закономерность мне увидеть не удалось, поэтому я забил.
Но у тех, кто отписался в этой теме метод несоизмеримо мощней — видимо следствие высокой математической культуры, с которой я не знаком, поэтому даже описать его не смогу.

Но главное в этом частном случае, как я понял из комментариев выше — это выразить F(N+1) через F(N)+<какие-то данные> (не уверен, что записано формально правильно).

Очевидно, это маленькая частность. Скажите, пожалуйста, как называется полный метод, можно ли его освоить, или это действительно целая культура? Тогда, все-таки, как она формируется.

Нечто похожее я встречал лишь однажды, но не уверен, что именно то — читал в читальном зале книгу Самарского по вычислительным методом, и там было что-то похожее про "рекурентные соотношения". По-моему, осуществлялся подобный вывод.

Здравствуйте, Аноним, Вы писали:


А>Очевидно, это маленькая частность. Скажите, пожалуйста, как называется полный метод, можно ли его освоить, или это действительно целая культура? Тогда, все-таки, как она формируется.

Рекуррентное соотношение.

Здравствуйте, Аноним, Вы писали:

А>Простую закономерность мне увидеть не удалось, поэтому я забил.
А>Но у тех, кто отписался в этой теме метод несоизмеримо мощней — видимо следствие высокой математической культуры, с которой я не знаком, поэтому даже описать его не смогу.

Эээ, закономерность. Столько всего с квадратами связано — и метод суммирования юного Гаусса, и производная параболы, и семейство алгоритмов Брезенхема.


А>Очевидно, это маленькая частность. Скажите, пожалуйста, как называется полный метод, можно ли его освоить, или это действительно целая культура? Тогда, все-таки, как она формируется.

А>Нечто похожее я встречал лишь однажды, но не уверен, что именно то — читал в читальном зале книгу Самарского по вычислительным методом, и там было что-то похожее про "рекурентные соотношения". По-моему, осуществлялся подобный вывод.

гуглить, например, "производящие функции"
Но в данном случае это из пушки по воробьям.

Спасибо!
Почувствовал мощь математики.

Здравствуйте, TarasB, Вы писали:

TB>У всех оотэнное говно
TB>возведите миллион в квадрат вашим способом и моим

У тебя слишком много переменных и не сделана концевая рекурсия.

Здравствуйте, Кодт, Вы писали:

К>У тебя слишком много переменных и не сделана концевая рекурсия.

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

Здравствуйте, TarasB, Вы писали:

TB>У тебя переменных больше. У меня ноль, у тебя одна.

То, что все твои переменные присваиваются единожды, ничего не значит. Их там не меньше 5 (для концевой рекурсии) или 4*log2(n) (для обычной).
А у меня, кстати, ровно две переменные.

Здравствуйте, Кодт, Вы писали:

К>То, что все твои переменные присваиваются единожды, ничего не значит. Их там не меньше 5 (для концевой рекурсии) или 4*log2(n) (для обычной).
К>А у меня, кстати, ровно две переменные.

А, так ты любую ячейку памяти считаешь переменной?
Ну тогда я могу свести свой к 4 переменным, если руками разверну цикл, определяющий двоичный логарифм множителя. Ну портянка из 63 ифов будет). А с появлением 128-битных процессоров её надо будет переписать.

Здравствуйте, TarasB, Вы писали:

TB>А, так ты любую ячейку памяти считаешь переменной?
TB>Ну тогда я могу свести свой к 4 переменным, если руками разверну цикл, определяющий двоичный логарифм множителя. Ну портянка из 63 ифов будет). А с появлением 128-битных процессоров её надо будет переписать.

Да. Указатель инструкции — это тоже переменная. А ты думал, будет легко?

Здравствуйте, Кодт, Вы писали:

К>Да. Указатель инструкции — это тоже переменная.

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

Кстати, твой код я могу увеличить на одну переменную, сделав портянку по степеням двойки ( n^2 = (n-2^m)^2 + 2*2^m*n — (2^m)^2 ). Одна лишняя переменная, зато алгоритмическое ускорение.
И ещё я понял, что достаточно разбирать лишь до 2^31, потому что дальше уже в квадрат не возводится, переполнение будет

Здравствуйте, TarasB, Вы писали:

TB>Указатель инструкции, регистр флагов, указатель на вершину стека... Тогда нифига у тебя не две переменные. Как именно ты их считаешь?

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

TB>Кстати, твой код я могу увеличить на одну переменную, сделав портянку по степеням двойки ( n^2 = (n-2^m)^2 + 2*2^m*n — (2^m)^2 ). Одна лишняя переменная, зато алгоритмическое ускорение.

Не понял, как считать по твоей формуле. Вот так получилось 5 переменных.

// n*n = n*2^k + n*(n-2^k)
int square(int n)
{
  int s = 0;
  int m = n; // правый множитель
  while(m > 0)
  {
    int p  = 1; // 2^k, k=0, 1, ...
    int pn = n; // p*n
    while(p+p <= m)
    {
      p  += p;
      pn += pn;
    }
    s += pn;
    m -= p;
  }
  return s;
}

TB>И ещё я понял, что достаточно разбирать лишь до 2^31, потому что дальше уже в квадрат не возводится, переполнение будет

Будем действовать, как gcc 4.8 -O2. "переполнения не бывает", а если оно происходит, то клиент ССЗБ.