Help with implementing an algorithm!

This is a discussion on Help with implementing an algorithm! within the C Programming forums, part of the General Programming Boards category; Hello there! The following is an implementation of the street numbers problem . My output stops at the fifth line! ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    103

    Help with implementing an algorithm!

    Hello there!
    The following is an implementation of the street numbers problem.
    My output stops at the fifth line! probably because of bad memory management or the size of the integers. I tried bigger types like long long but the problem persists.
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    int main(int args, char* argv[]){
                 int sum1, sum2;
                 int count = 0;
                 int max = 8;
                 int temp = 0;
                 while(count < 10){
                             temp =  (max * (max + 1) / 2);
                             for (int house = 1 ; house <=max ; house++){
                                 sum1 = house * (house - 1) / 2;
                                 sum2 =temp - house - sum1; 
                                 if (sum1 == sum2){
                                                 printf("%d\t%d\n",house,max);
                                                 count++;
                                                 }
                                 }
                             max++;
                             }
                 printf("\t\t\tEnd of Program\n\t\t\t");
                 system("PAUSE");
        }

  2. #2
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Code:
    for (int house = 1 ; house <=max ; house++){
    Declare house where all other variables are declared i.e remove 'int' from the for loop.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Already tried. The problem still takes a long time to execute the 6th line of input. I've waited a little bit, and it gave me strange results:
    6 8
    35 49
    204 288
    1189 1681
    6930 9800
    256 131072
    7742 131528
    11707 132113
    19813 134033
    115619 134705
    Normally it should display:
    6 8
    35 49
    204 288
    1189 1681
    6930 9800
    40391 57121
    235416 332928
    1372105 1940449
    7997214 11309768
    46611179 65918161
    Any hints? I think it has to do with some kind of over-calculation!

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Quote Originally Posted by BEN10 View Post
    Code:
    for (int house = 1 ; house <=max ; house++){
    Declare house where all other variables are declared i.e remove 'int' from the for loop.
    Wait what?! You just suggested a change that has no effect other than it's worse style?

    Part of the calculation for temp: 57121 * (57121 + 1) overflows the maximum positive value that an integer can hold: 2147483641. An "unsigned int" goes up to twice as large, but that still wont get you near ten entries.
    Does your compiler support "long long"? Post the code that has "long long" and the output.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by iMalc View Post
    Wait what?! You just suggested a change that has no effect other than it's worse style?
    What I suggested was after my compiler gave me error because of 'int' inside the for loop. After all what's "worse" if we declare house where other variables have been declared!!!
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  6. #6
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,409
    i put it in the debugger for a quick spin, i am not very good at reading it but when watching the variables a random 'variable' shows "65 = 5" around the time the program hangs.
    Last edited by rogster001; 09-04-2009 at 03:03 AM.

  7. #7
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    Quote Originally Posted by BEN10 View Post
    What I suggested was after my compiler gave me error because of 'int' inside the for loop. After all what's "worse" if we declare house where other variables have been declared!!!
    this is one difference between C90 and C99
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,409

    overflow

    Part of the calculation for temp: 57121 * (57121 + 1) overflows the maximum positive value that an integer can hold: 2147483641
    i suppose i should have watched the variables a bit longer....!

  9. #9
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Ok. I did as told. I changed temp type to long long but I still get the same output as above!
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    int main(int argc, char* argv[]){
                 long long sum1, sum2;
                 int count = 0;
                 int max = 8;
                 long long temp = 0;
                 int house;
                 while(count < 10){
                             temp =  (max * (max + 1) / 2);
                             for (house = 1 ; house <=max ; house++){
                                 sum1 = house * (house - 1) / 2;
                                 sum2 =temp - house - sum1; 
                                 if (sum1 == sum2){
                                                 printf("%d\t%d\n",house,max);
                                                 count++;
                                                 }
                                 }
                             max++;
                             }
                 printf("\t\t\tEnd of Program\n\t\t\t");
                 system("PAUSE");
                 return 0;
        }

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You can't print a long long with %d. %lld, maybe.

  11. #11
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    I tried what you said tabstop. Still, no output after the 6th line. I undersand the problem with int, but long long didn't fix it.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Two posts about those contests at the same day... I miss being in university...

    Now, there is one quite common way to solve problems with a small set of possible inputs, or like this case no input at all: precompute it.
    Ah, I remember the good old days on a contest. We had a way too slow solution. But there could only be 100 possible inputs or so. What did we do? Have the program run for 5 minutes and output all solutions followed by a comma. Copy-paste into a new file, into an array with 100 elements, and for whatever input you receive simply output the value the array contains.
    Of course, that's only possible with less than about 1000 possible inputs, which is not too common.

    In this case you don't have any input at all. What my answer would look like?
    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
    cout<<"6 8"<<endl;
    cout<<"35 49"<<endl;
    cout<<"204 288"<<endl;
    cout<<"1189 1681"<<endl;
    cout<<"6930 9800"<<endl;
    cout<<"40391 57121"<<endl;
    cout<<"235416 332928"<<endl;
    cout<<"1372105 1940449"<<endl;
    cout<<"7997214 11309768"<<endl;
    cout<<"46611179 65918161"<<endl;
    }
    Actually the output format is wrong, but I'm too lazy to fix that. During the contest you might even pass with a presentation error.

    Remember, if you are going to join the contest: you don't have any time. 5 hours sounds like a lot, but it's not nearly enough to solve most problems (especially not with team mates like I had). So a good team is important as well .

  13. #13
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Yes, thank you.
    Such a solution is lovely, but I'm just trying to solve the problem for my self. So it's really important for me to know what went wrong in my code. Later on, I'll think on doing some math work to make it more efficient. Right now, help me see where this lost it!

  14. #14
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Leojeen View Post
    Yes, thank you.
    Such a solution is lovely, but I'm just trying to solve the problem for my self. So it's really important for me to know what went wrong in my code. Later on, I'll think on doing some math work to make it more efficient. Right now, help me see where this lost it!
    Well, I did some math and it can be a LOT more efficient. In the meantime, your problem:
    Code:
    sum1 = house * (house - 1) / 2;
    As "house" is an int, it will still overflow. Only after the overflow is it converted to a long long. Another advice for programming contests: unless you have to, don't think too much about the types. If you need a long long somewhere, stop using normal integers at all (unless you have huge arrays where it doesn't matter but the extra memory usage would matter).

  15. #15
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Ok. This is giving me a headache. I used long long everywhere when I deemed necessary.
    Now I get 0s for the max value. Very strange.
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    int main(int argc, char* argv[]){
                 long long sum1, sum2;
                 int count = 0;
                 long long max = 8;
                 long long temp = 0;
                 long long house;
                 while(count < 10){
                             temp =  (max * (max + 1) / 2);
                             for (house = 1 ; house <=max ; house++){
                                 sum1 = house * (house - 1) / 2;
                                 sum2 =temp - house - sum1; 
                                 if (sum1 == sum2){
                                                 printf("%lld\t%lld\n",house,max);
                                                 count++;
                                                 }
                                 }
                             max++;
                             }
                 printf("\t\t\tEnd of Program\n\t\t\t");
                 system("PAUSE");
                 return 0;
        }
    With the program still overflowing irght after the 6th line.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. implementing an hours counting algorithm
    By droseman in forum C Programming
    Replies: 6
    Last Post: 02-04-2009, 02:59 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Replies: 2
    Last Post: 10-18-2002, 08:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21