For Pro Coders!

pabloaimer · 04-30-2007, 03:00 AM

well ..
i am facing a problem and i hope pro coders here can gimme some help
there is a monthly test for coders here in egypt in my city ..
and i was given a question , i solved .. but as they commented ' in a bad way '
the problem was :
create a program where the user will give x , n
and the program must give him the result of this sequence:
1 + 1/x^1 + 2/x^2 + 3/x^3 + 4/x^4 ..... + n/x^n
btw : this ^ means power ..

well .. its not a very hard question ..
i solved it by giving them in the test this code:

===================================

Code:

#include <stdio.h>
#include <math.h>
main()
{
double x,n,b,y=1;
printf("Write The Value Of x: ");
scanf("%lf",&x);
printf("Write The Value Of n: ");
scanf("%lf",&n);
for(b=1;b<=n;b++)
y+=b/(pow(x,b ));
printf("y Equals %lf\n",y);
getchar();
}

===================================

this solution worked perfectly the question ..
but they gave me 5 out of 10
when i went to ask them
they told me .. dont panic .. no one solved this question like we was expected ..
they told me the computer will solve this equation like this
he will solve at x ( as for power 1 )and then x*x ( as for power 2 )and then x*x*x ( as for power 3 )and then x*x*x*x ( as for power 4)

they told me imagine the input number of n was a million 1000000
the computer will take minutes to solve it
which is a big time ..
they told me try to solve it where if we input million the computer solve it in a second normally
i told they give me a hint
he told me ..
instead if the computer making x ( as for power 1 )and then x*x ( as for power 2 )and then x*x*x ( as for power 3 )and then x*x*x*x ( as for power 4)
the computer can make it easier .. if the computer already made x*x*x .. why making again x*x*x*x , why not making the computer use the before equation .. he already timed x*x*x , why not just multiplying just another one x
this will save a lot of the memory of the program ..
well ..
i thought a lot
i cant find a solution ..
do u think if we made it for example multiplying every time with 1/x ?? but what about the n ?
anyone have an idea ??
sure you pro coders wont have a problem in doing this
many thanks guys
peace

i am sure grizzlybear can help me ..
hes a decent coder ..
and he also likes c and hate c++
just like me

KONI · 04-30-2007, 04:46 AM

This is the same difference between the recursive factorial and the dynamic programming factorial. During each iteration of your loop, you are actually calculating the entire power again, completely forgetting about the values you already calculated the iteration before.

An optimized version is the following:

Code:

#include <stdio.h>
#include <math.h>
main()
{
double x,n,b,y,z=1;
printf("Write The Value Of x: ");
scanf("%lf",&x);
printf("Write The Value Of n: ");
scanf("%lf",&n);

for(b=1;b<=n;b++)
{
    z *= x;
    y+=b/z;
}

printf("y Equals %lf\n",y);
getchar();
}

pabloaimer · 04-30-2007, 05:49 AM

i would like to thank you very very very much for helping me
and i aperciate that u lost ur time thinking in my problem ..
many thanks for u .. thats first ..
secondly ..
sir .. i beleive that u didnt solve the problem by this ..
sir .. trace with me the program ..
lets say x = 2
and z = 2
in my old program .. ( the one that takes too much memory because it repeats the multiplaction.)

what will happen ?
1 + 1/2 + 2/4
so y= 2

in the other hand ..
by using ur optimzed version ..
z is a constant varaible that equals to 1
every time its multiplied by x
( please notice that the x and z doesnt change .. the x remains its value .. and the z remains its value .. every time its multpiled by x which is constant , so z will be constant! the only changing values in our program is b , every loop b is increased by 1 )
x =2 in our tracing
1 *2 = 2
ok ?
so z =2
and its equal 2 every loop .. its doesnt change
so lets trace ..
the first loop
y = y + b/z
therefore
y = 1 + 1/2
y=1.5 ( stored in memory as new value of y and will be used in the next loop )
in the second and last loop ( becoz n = 2 in our tracing )
y = 1.5 + 2/2
= 2.5
sir .. does 2 = 2.5 ??
your new optimzed version doesnt give us the right value
the right value of sequnce is 2 !!
1 + 1/2 + 2/4
= 2

there is something wrong in your code sir ..
i beleive u are a great coder because u solved my problem very fast .. but maybe u didnt have time to trace and test your code ..

many many many thanks .. i cant beleive you are helping me for free
thank you

Kind Regards,
pabloaimer

pabloaimer · 04-30-2007, 05:59 AM

NO NO NO !!
YOU WERE RIGHT !!
it worked it worked !!
ur code was a optimzed right version
but u made a very small mistake
the value of y <--
u didnt put the value of y
u must write y=1 in the declartion
thanks brother

or i should call u my teacher .. and my teacher = my master

many thanks ..

KONI · 04-30-2007, 06:06 AM

Yes, I made a small mistake, the correct line is ofc:

Code:

double x,n,b,y=1,z=1;

pabloaimer · 04-30-2007, 06:23 AM

sir koni ..i sent to my test center .. and they confirmed that its the right solution .. and they confirmed i am the first one in my city to send the right solution

thanks for helping me ..
but sir .. i feel i am little idiot ..
i cant understand what we have done !!

the z is constant by this .. if x was 4 , the z = 1 * 4
then the z = 4
always 4
and y = 1 + b/z
means
the sequence will be
1 + 2/4 = 1.5
the next loop
1.5 + 2/4
equals = 2
the third loop
2+ 3/4
equals 2.75
... etc

yes i know it gives the right answer and the same answer the old code used to give .. but sir .. i cant understand what did u put ..
can u teach me slowly what u did ?
many thanks and regards

redche · 04-30-2007, 08:45 AM

z is not a constant , notice that each iteration of the loop z is change
z*=x;
for x = 4 the result would be
b=1 : z=1*4=4
b=2 : z=z*4=4*4^2
etc

KONI · 04-30-2007, 09:51 AM

z is not constant but multiplied each iteration by x, which gives the same result than the pow() but doesn't have to be recalculated each time. Maybe you understand it better if I'd write:

Code:

#include <stdio.h>
#include <math.h>
main()
{
double x,n,b,y=1,z=1;
printf("Write The Value Of x: ");
scanf("%lf",&x);
printf("Write The Value Of n: ");
scanf("%lf",&n);

for(b=1;b<=n;b++)
{
    z = z * x;
    y+=b/z;
}

printf("y Equals %lf\n",y);
getchar();
}

pabloaimer · 04-30-2007, 09:58 AM

yes sir ..
i understood now
although i know that z*= x means that z = z * x
but i got confused in the middle
now everything clear
thank you sir ..

04-30-2007, 03:00 AM	#1
pabloaimer Registered User Join Date: Apr 2007 Posts: 5	For Pro Coders! well .. i am facing a problem and i hope pro coders here can gimme some help there is a monthly test for coders here in egypt in my city .. and i was given a question , i solved .. but as they commented ' in a bad way ' the problem was : create a program where the user will give x , n and the program must give him the result of this sequence: 1 + 1/x^1 + 2/x^2 + 3/x^3 + 4/x^4 ..... + n/x^n btw : this ^ means power .. well .. its not a very hard question .. i solved it by giving them in the test this code: =================================== Code: #include <stdio.h> #include <math.h> main() { double x,n,b,y=1; printf("Write The Value Of x: "); scanf("%lf",&x); printf("Write The Value Of n: "); scanf("%lf",&n); for(b=1;b<=n;b++) y+=b/(pow(x,b )); printf("y Equals %lf\n",y); getchar(); } =================================== this solution worked perfectly the question .. but they gave me 5 out of 10 when i went to ask them they told me .. dont panic .. no one solved this question like we was expected .. they told me the computer will solve this equation like this he will solve at x ( as for power 1 )and then xx ( as for power 2 )and then xxx ( as for power 3 )and then xxxx ( as for power 4) they told me imagine the input number of n was a million 1000000 the computer will take minutes to solve it which is a big time .. they told me try to solve it where if we input million the computer solve it in a second normally i told they give me a hint he told me .. instead if the computer making x ( as for power 1 )and then xx ( as for power 2 )and then xxx ( as for power 3 )and then xxxx ( as for power 4) the computer can make it easier .. if the computer already made xxx .. why making again xxxx , why not making the computer use the before equation .. he already timed xx*x , why not just multiplying just another one x this will save a lot of the memory of the program .. well .. i thought a lot i cant find a solution .. do u think if we made it for example multiplying every time with 1/x ?? but what about the n ? anyone have an idea ?? sure you pro coders wont have a problem in doing this many thanks guys peace i am sure grizzlybear can help me .. hes a decent coder .. and he also likes c and hate c++ just like me
pabloaimer is offline

04-30-2007, 04:46 AM	#2
KONI Lean Mean Coding Machine Join Date: Mar 2007 Location: Luxembourg, Europe Posts: 444	This is the same difference between the recursive factorial and the dynamic programming factorial. During each iteration of your loop, you are actually calculating the entire power again, completely forgetting about the values you already calculated the iteration before. An optimized version is the following: Code: #include <stdio.h> #include <math.h> main() { double x,n,b,y,z=1; printf("Write The Value Of x: "); scanf("%lf",&x); printf("Write The Value Of n: "); scanf("%lf",&n); for(b=1;b<=n;b++) { z *= x; y+=b/z; } printf("y Equals %lf\n",y); getchar(); }
KONI is offline

04-30-2007, 05:49 AM	#3
pabloaimer Registered User Join Date: Apr 2007 Posts: 5	i would like to thank you very very very much for helping me and i aperciate that u lost ur time thinking in my problem .. many thanks for u .. thats first .. secondly .. sir .. i beleive that u didnt solve the problem by this .. sir .. trace with me the program .. lets say x = 2 and z = 2 in my old program .. ( the one that takes too much memory because it repeats the multiplaction.) what will happen ? 1 + 1/2 + 2/4 so y= 2 in the other hand .. by using ur optimzed version .. z is a constant varaible that equals to 1 every time its multiplied by x ( please notice that the x and z doesnt change .. the x remains its value .. and the z remains its value .. every time its multpiled by x which is constant , so z will be constant! the only changing values in our program is b , every loop b is increased by 1 ) x =2 in our tracing 1 *2 = 2 ok ? so z =2 and its equal 2 every loop .. its doesnt change so lets trace .. the first loop y = y + b/z therefore y = 1 + 1/2 y=1.5 ( stored in memory as new value of y and will be used in the next loop ) in the second and last loop ( becoz n = 2 in our tracing ) y = 1.5 + 2/2 = 2.5 sir .. does 2 = 2.5 ?? your new optimzed version doesnt give us the right value the right value of sequnce is 2 !! 1 + 1/2 + 2/4 = 2 there is something wrong in your code sir .. i beleive u are a great coder because u solved my problem very fast .. but maybe u didnt have time to trace and test your code .. many many many thanks .. i cant beleive you are helping me for free thank you Kind Regards, pabloaimer
pabloaimer is offline

04-30-2007, 05:59 AM	#4
pabloaimer Registered User Join Date: Apr 2007 Posts: 5	NO NO NO !! YOU WERE RIGHT !! it worked it worked !! ur code was a optimzed right version but u made a very small mistake the value of y <-- u didnt put the value of y u must write y=1 in the declartion thanks brother or i should call u my teacher .. and my teacher = my master many thanks ..
pabloaimer is offline

04-30-2007, 06:06 AM	#5
KONI Lean Mean Coding Machine Join Date: Mar 2007 Location: Luxembourg, Europe Posts: 444	Yes, I made a small mistake, the correct line is ofc: Code: double x,n,b,y=1,z=1;
KONI is offline

04-30-2007, 06:23 AM	#6
pabloaimer Registered User Join Date: Apr 2007 Posts: 5	sir koni ..i sent to my test center .. and they confirmed that its the right solution .. and they confirmed i am the first one in my city to send the right solution thanks for helping me .. but sir .. i feel i am little idiot .. i cant understand what we have done !! the z is constant by this .. if x was 4 , the z = 1 * 4 then the z = 4 always 4 and y = 1 + b/z means the sequence will be 1 + 2/4 = 1.5 the next loop 1.5 + 2/4 equals = 2 the third loop 2+ 3/4 equals 2.75 ... etc yes i know it gives the right answer and the same answer the old code used to give .. but sir .. i cant understand what did u put .. can u teach me slowly what u did ? many thanks and regards
pabloaimer is offline

04-30-2007, 08:45 AM	#7
redche Registered User Join Date: Apr 2007 Posts: 15	z is not a constant , notice that each iteration of the loop z is change z=x; for x = 4 the result would be b=1 : z=14=4 b=2 : z=z4=44^2 etc
redche is offline

04-30-2007, 09:51 AM	#8
KONI Lean Mean Coding Machine Join Date: Mar 2007 Location: Luxembourg, Europe Posts: 444	z is not constant but multiplied each iteration by x, which gives the same result than the pow() but doesn't have to be recalculated each time. Maybe you understand it better if I'd write: Code: #include <stdio.h> #include <math.h> main() { double x,n,b,y=1,z=1; printf("Write The Value Of x: "); scanf("%lf",&x); printf("Write The Value Of n: "); scanf("%lf",&n); for(b=1;b<=n;b++) { z = z * x; y+=b/z; } printf("y Equals %lf\n",y); getchar(); }
KONI is offline

04-30-2007, 09:58 AM	#9
pabloaimer Registered User Join Date: Apr 2007 Posts: 5	yes sir .. i understood now although i know that z= x means that z = z x but i got confused in the middle now everything clear thank you sir ..
pabloaimer is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
half life 2 modification looking for coders	pantsOFFinPUBLI	Projects and Job Recruitment	0	07-28-2005 01:32 AM
PROJECTLESS C++/VC++ coders, please read this.	codefx	Projects and Job Recruitment	2	01-14-2005 12:53 PM
Coders	askala_mud	Projects and Job Recruitment	2	12-09-2004 06:39 AM