Чтобы вычислить теорему Эйлера о пятиугольных числах с помощью динамического программирования

Вот ссылка на код, и я также разместил ее ниже.

 #include<math.h>
void pentagon(int n)
 {
    int k,p[10],a[10],b[10];
    if(n<0)
      p[n]=0;
    if(n==0)
      p[n]=1;
    for(k=1;k<n;k++)
     {
        a[k]=((3*pow(k,2))-k)/2;
        b[k]=((3*pow(k,2))+k)/2;
     }
    for(k=1;k<n;k++)
     {
       p[n]=pow(-1,k-1)(pentagon(n-a[k])+pentagon(n-b[k]));
     }
   cout<<p[n];
 }
 int main()
 {
   pentagon(4);
   return(0);
 }

Я получаю следующую ошибку:
В функции 'void pentagon(int)': Строка 11: ошибка: вызов перегруженного 'pow(int&, int)' является неоднозначной компиляцией, завершенной из-за -Wfatal-ошибок


c++ dynamic-programming pow
person Ava    schedule 11.03.2011    source источник
comment
Кроме того, вы также можете изменить строку 16 на p[n]=pow(-1,k-1)*(pentagon(n-a[k])+pentagon(n-b[k])); (обратите внимание на *) или что-то подобное. Другая ошибка заключается в том, что pentagon ничего не возвращает (пока?), но вы используете ее как функцию, возвращающую int.   -  person schnaader    schedule 11.03.2011
comment
codepad.org/7f663Q1C после изменения.. Ошибки: cc1plus: предупреждения рассматриваются как ошибки В функции 'int pentagon( int)': Строка 11: предупреждение: преобразование в 'int' из 'double' Строка 12: предупреждение: преобразование в 'int' из 'double' Строка 16: ошибка: вызов перегруженного 'pow(int, int)' неоднозначен компиляция прекращена из-за -Wfatal-ошибок.   -  person Ava    schedule 11.03.2011
comment
Вы можете заменить pow(k,2) на (k * k). Как правило, основные арифметические функции выполняются быстрее, чем вызов более сложных функций.   -  person Thomas Matthews    schedule 11.03.2011
comment
Отредактировано одно: codepad.org/vm5d0Lr8 ......cc1plus: предупреждения рассматриваются как ошибки в функции ' int pentagon(int)': Строка 11: предупреждение: преобразование в 'int' из 'double' Строка 12: предупреждение: преобразование в 'int' из 'double' Строка 16: предупреждение: преобразование в 'int' из 'double'   -  person Ava    schedule 11.03.2011
comment
@ Томас, да, но для другого цикла он мне понадобится.   -  person Ava    schedule 11.03.2011
comment
Выражение pow(-1, k-1) кажется странным. Это эквивалентно 1/pow(-1, k). Знаменатель либо 1, либо -1. Так почему показатель степени отрицательный? Это выражение можно заменить на (k % 2) ? -1 : 1. Я что-то пропустил?   -  person Thomas Matthews    schedule 11.03.2011
comment
Массив p не нужен и может быть заменен одной переменной. Во время рекурсии ни одно из предыдущих значений не запоминается; это как новый чистый лист. Кроме того, p[n] никогда не упоминается (в правой части) каких-либо выражений (за исключением cout). Таким образом, его можно упростить до одной переменной p. Если ваша функция закодирована неправильно.   -  person Thomas Matthews    schedule 11.03.2011
comment
@Thomas: Нет, pow(-1, k-1) правильно. Он вернет -1 для четных, 1 для нечетных k. И я думаю, что использование p в качестве массива правильно для динамического программирования, но здесь действительно не имеет смысла (также см. вывод моего ответа, показывающий, что что-то не так). p, возможно, должен быть глобальным, но это тоже мало помогает.   -  person schnaader    schedule 11.03.2011
comment
@Все Спасибо за помощь. Я понял, но не уверен, правильно ли я понял теорему Эйлера. Вопрос заключается в следующем. Еще одна повторяемость для p(n), являющаяся следствием теоремы Эйлера о пятиугольных числах, заключается в следующем. p(n) = 0, если n ‹ 0 ;1 P, если n = 0 ;(−1)k−1(p(n − ak) + p(n − bk)) в противном случае, где ak = (3k^2 − k )/2 , bk =(3k^2 + k)/2 Используйте это повторение для вычисления p(n) с помощью динамического программирования только с одномерным массивом. Где я ошибся в понимании проблемы?   -  person Ava    schedule 11.03.2011
comment
Извините, но эта функция меня глючит. В последнем цикле for индекс для p никогда не меняется. Вы также можете упростить его, чтобы он использовал последнее значение k в итерации, то есть n. Замена n на k приводит к интересному упрощению, указывая на то, что предыдущий цикл for также можно упростить.   -  person Thomas Matthews    schedule 11.03.2011

Ответы (4)


arrow_upward
2
arrow_downward

Замените 2 на 2.0 в качестве второго аргумента pow (строки 11, 12).

См. также: http://www.cplusplus.com/reference/clibrary/cmath/pow/

person miku    schedule 11.03.2011
comment
Кроме того, в строке 16 есть вызов pow, где должно быть pow(-1,(double)(k-1)) или pow(-1,k-1.0). - person schnaader; 11.03.2011
comment
Сделал так, все равно ошибка. cc1plus: предупреждения обрабатываются как ошибки В функции 'int pentagon(int)': Строка 11: предупреждение: преобразование в 'int' из 'double' Строка 12: предупреждение: преобразование в 'int' из 'double' Строка 16: ошибка: вызов перегруженного 'pow(int, int)' является неоднозначной компиляцией, прерванной из-за -Wfatal-ошибок. Измененный код: codepad.org/7f663Q1C. - person Ava; 11.03.2011
comment
Отредактировано одно: codepad.org/vm5d0Lr8 ......cc1plus: предупреждения рассматриваются как ошибки в функции ' int pentagon(int)': Строка 11: предупреждение: преобразование в 'int' из 'double' Строка 12: предупреждение: преобразование в 'int' из 'double' Строка 16: предупреждение: преобразование в 'int' из 'double' - person Ava; 11.03.2011
comment
См. фрагмент кода @schnaader — он компилируется без ошибок и предупреждений. - person miku; 11.03.2011

arrow_upward
1
arrow_downward

Сбор и исправление всех ошибок (и предупреждений) приводит к следующему коду (codepad). Я сделал несколько комментариев о том, что изменилось.

#include <math.h>
#include <iostream> // Some compilers will complain if missing

using namespace std; // Some compilers will complain if missing

// returns int instead of being void
int pentagon(int n)
 {
    int k,p[10],a[10],b[10];
    // recursion end - we want to jump out here right away
    if(n<0) return 0;
    if(n==0) return 1;
    for(k=1;k<n;k++)
     {
        a[k]=((3*(int)pow(k,2.0))-k)/2; // pow needs double as second argument
        b[k]=((3*(int)pow(k,2.0))+k)/2; //   and returns double
     }
    for(k=1;k<n;k++)
     {
       // pow casting and double as second argument, multiplication with pentagon
       p[n]=(int)pow(-1,k-1.0)*(pentagon(n-a[k])+pentagon(n-b[k]));
     }
   cout<<p[n]<<endl; // cleaner output
   return p[n]; // return the calculated value
 }
 int main()
 {
   pentagon(4);
   return(0);
 }

но я предполагаю, что основной алгоритм все еще неверен, так как вывод:

-1084535312
-1084535311
1074838088
0
3
4
0
person schnaader    schedule 11.03.2011
comment
Он отлично компилируется. Чтобы избавиться от предупреждений cout, мне просто нужно было включить обычные #include <iostream> и using namespace std;. - person miku; 11.03.2011
comment
Логическую часть я увижу, но я все еще не понимаю даже этого. - person Ava; 11.03.2011
comment
@miku: Спасибо, тоже исправил, изначально не было, потому что codepad не жаловался, но так чище. - person schnaader; 11.03.2011

arrow_upward
0
arrow_downward

Вот некоторые ошибки или улучшения, которые я заметил:

Добавлен iostream и использование пространства имен std:

#include <cmath>
#include <iostream>
using namespace std;

Изменено pow(k,2) на k*k:

a[k]=((3*(k*k))-k)/2;
b[k]=((3*(k * k))+k)/2;

Добавьте символ умножения к назначению p[n]:

p[n] = pow(-1.0,k-1) * (pentagon(n-a[k]) + pentagon(n-b[k]));

Метод pentagon должен возвращать значение, чтобы использовать его в приведенном выше выражении.

person Thomas Matthews    schedule 11.03.2011

arrow_upward
0
arrow_downward

Вам не хватает суммирования части уравнения. См. http://en.wikipedia.org/wiki/Pentagonal_number_theorem.

Ваша функция pentagon вычисляет только один термин за раз. Не существует кода, суммирующего все термины.

person Thomas Matthews    schedule 11.03.2011