473,324 Members | 2,257 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

in c++ how to compute the value of Pn by this formula

6
so can anyone tell me how to proceed on writing a function that uses bottom-up dynamic programming approach to compute the value of Pn defined by the recurrence:
P_n= floor(n/2) + P floor(n/2) + P ceil(n/2) for n>=1 with P_1=1

floor() is the function that rounds a number down.
ceil() is the function that rounds a number up.

sample manual calculation of the sequence would be:

P_2=floor(2/2) + P floor(2/2) + P ceil(2/2)= 1 + P1 + P1= (1+1+1) = 3

I really don't know how to proceed writing this function. Thanks in advance.
Jun 6 '09 #1
7 1737
Banfa
9,065 Expert Mod 8TB
Look up recursion/recursive functions. have an attempt at the problem yourself, the maths library has ceiling and floor functions look up math.h.
Jun 7 '09 #2
JosAH
11,448 Expert 8TB
Also note than if n is even then floor(n/2) == ceil(n/2); otherwise ceil(n/2) == floor(n/2)+1. This allows for a simple interval definition of P:

P(n) == if n even then n/2+P(n/2)+P(n/2)
else n/2+P(n/2)+P(n/2+1)

where '/' denotes integer division, i.e.

P(1) == 1
P(2) == 1+P(1)+P(1)
P(3) == 1+P(1)+P(2)
P(4) == 2+P(2)+P(2)
P(5) == 2+P(2)+P(3)
P(6) == 3+P(3)+P(3)
P(7) == 3+P(3)+P(4)
P(8) == 4+P(4)+P(4)
etc.

kind regards,

Jos
Jun 7 '09 #3
star33
6
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
int p[100];
p[0]=0;
p[1]=1;

int n=0;
for(int i=2; i<=n;i++)
{
if(n % 2 == 0)
{
return n + floor(n/2) + ceil(n/2);
}
else
{
return n + (floor(n/2) + 1) + ceil(n/2);
}
}

return 0;
}
could anyone tell me is this the right logic? thanks for the help. I am getting an error that says floor anbiguos call to overloaded function.
Jun 8 '09 #4
JosAH
11,448 Expert 8TB
Did you read my previous reply? You don't need the floor() and ceil() functions. The integer division operator will do.

kind regards,

Jos
Jun 8 '09 #5
newb16
687 512MB
The logic is wrong, because it immediately returns from main and stops calculation on the first iteration. Let alone it doesn't compile.
Jun 8 '09 #6
star33
6
Expand|Select|Wrap|Line Numbers
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int p[100];
  7.     p[0]=0;
  8.     p[1]=1;
  9.  
  10.     int n=0;
  11.     for(int i=2; i<=n;i++)
  12.     {
  13.  
  14.         if(n % 2 == 0)
  15.         {
  16.             n=(n/2) + p(n/2) + p(n/2);
  17.  
  18.         }
  19.         else
  20.         {
  21.             n=(n/2) + p(n/2) + p((n/2)+1);
  22.  
  23.         }
  24.     }
  25.     system("pause");
  26.     return 0;
  27. }
  28.  
so using integer division operator. what am I missing? any suggestions. Thank
for the help
Jun 8 '09 #7
donbock
2,426 Expert 2GB
Look closely at your 'for' loop. How many times will the body of the loop be executed? How many times do you want it to execute?

Do you care whether you end up with an iterative or a recursive function? A 'for' loop suggests that you're aiming for an iterative function.

By the way, it would be helpful if you enclosed your source code in CODE tags.
Jun 8 '09 #8

Sign in to post your reply or Sign up for a free account.

Similar topics

1
by: Evgeny Gopengauz | last post by:
For example, I have a table FORMULA_TABLE with the column FORMULA which contains some function y=f(x) in its symbol description like '@X*2+1' create table FORMULA_TABLE( ID int, FORMULA...
5
by: Charles Law | last post by:
Hi folks Not really a .NET question, but I always think this is a good place to ask. Does anyone have a favourite algorithm for determining the similarity of, or difference between two...
22
by: Richard | last post by:
I've really tried searching for this before I thought of bother you guys with this question. It's such a simple thing, but it's driving me nuts! Is it possible to check if an int (or any other...
6
by: Spoon | last post by:
Hello, Consider: #define BUFFER_SIZE 1234 /* or some other value */ uint8_t buffer; int do_stuff(uint8_t *buf); where do_stuff() does something with each octet in the buffer.
22
by: MLH | last post by:
If 3 things can be in one of 2 states, the number of possible combinations is equal to 2^3. But if I have 3 things, 2 of which can be in 2 states and the other in 3 states, what's the simplest...
7
by: eliss | last post by:
I'm using dl.call() to call a C function in an external library. It's working great so far except for one function, which returns an unsigned int in the C version. However, in python it returns a...
7
by: xirowei | last post by:
Let's say i create a String array that store 4 Alphabets {"A","B","C","D"} How can i get the result if i need permutation of 4P3 and 4P2? I had refer to many examples from the internet, but...
0
by: ccarter45 | last post by:
I need to compute the differences in color between 2 pictures. Also, I need to write a method that computes a useful difference color of two colors (where the colors and their difference will be...
2
by: JP Romano | last post by:
I'm sure I'm going to kick myself for this, but I just can't get the syntax right. Perhaps I'm a wee bit fried... anyway, hopefully one of you experts can set me straight again. All I'm trying to...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.