
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 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

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();
}

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

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 ..

Yes, I made a small mistake, the correct line is ofc:
Code:
double x,n,b,y=1,z=1;

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 :)

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

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();
}

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 ..