Thread: For Pro Coders!

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

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    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("&#37;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();
    }

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

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

  5. #5
    Lean Mean Coding Machine KONI's Avatar
    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;

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

  7. #7
    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=1*4=4
    b=2 : z=z*4=4*4^2
    etc

  8. #8
    Lean Mean Coding Machine KONI's Avatar
    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("&#37;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();
    }

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

Popular pages Recent additions subscribe to a feed

Similar Threads

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