Like Tree4Likes
  • 1 Post By Crossfire
  • 1 Post By King Mir
  • 1 Post By King Mir
  • 1 Post By phantomotap

C Program

This is a discussion on C Program within the C Programming forums, part of the General Programming Boards category; Hey guys, I was wondering how difficult of a Program this is and around how much time it would be ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    27

    C Program

    Hey guys, I was wondering how difficult of a Program this is and around how much time it would be expected to complete it.



    1. Traveling Salesperson Problem

    2. We have talked about the Traveling Salesperson Problem in class.
    3. For this assignment, you are to read an input file that gives the
    4. distances between each possible pair of "cities" for a traveling
    5. sales problem and then compute the cost of a "legal" tour. Again,
    6. as defined in class, a legal tour of N cities starts at any one of them
    7. and visits each of the other cities exactly once before returning to
    8. the original destination city. And the cost of a tour is the sum of
    9. the "distances" between adjacent cities in the tour.

    10. Your program output should print out the cost of the legal tour (or path) and
    11. also list the "cities" (well the integers associated with those cities) in the
    12. order visited. So, given data for a 4-city (Dallas, New York, Boston) the legal
    13. tours are:

    14. Dallas, New York, Los Angeles, Boston, Dallas
    15. Dallas, Boston, New York, Dallas
    16. New York, Dallas, Boston, New York
    17. New York, Boston, Dallas, New York
    18. Boston, New York, Dallas, Boston
    19. Boston, Dallas, New York, Boston

    20. and if we assume that the "cost" (or distance) or is represented as

    21. Dallas to New York is 1900 miles
    22. Boston to Dallas is 1950 miles
    23. New York to Boston 150 miles
    24. Los Angeles to Dallas is 1400 miles
    25. Los Angeles to Boston is 3150 miles
    26. Los Angeles to New York is 3100 miles

    27. your answer might be something like

    28. The tour New York, Dallas, Boston, Los Angeles New York costs 7150.

    29. which would represent the sum of 1900 (New York to Dallas), 1950 (Dallas to Boston),
    30. 3150 (Boston to Los Angeles) and 3100 (Los Angeles to New York). However, we'll
    31. "generalize" both our input and output to use consecutive integers, starting at 1,
    32. to represent the cities of the tour.

    33. NOTE: For the example data given, 7150 would not be the minimal cost tour. For
    34. example, the tour Los Angeles, Dallas, Boston, New York, Los Angeles would
    35. cost only 6600. However, for THIS program you're not required to come up
    36. with a minimal cost tour, just a legal tour. Any legal tour will do.

    37. Requirements:

    38. Your C program should consist of the single file, X.c (or whatever
    39. you decide to call your program.)

    40. Your program will read an input file (from stdin) which includes
    41. an unspecified number of command lines which describe the problem.
    42. The input (file) will contain two types of commands,
    43. and each command will be included on a single line of the file. The
    44. commands are:

    45. c W
    46. a X Y Z

    47. for Create a city and Add an edge between two cities. The symbols
    48. W,X,Y,Z all stand for "arbitrary" integers. Each "city" will be
    49. "named" with a distinct integer, specifically the one included in
    50. the "c" command. In the "a" command (add an edge) the edge should
    51. be From X To Y, with Cost Z. To make the program a bit easier,
    52. all the "Create" commands will precede any "Add" commands in the input
    53. file. If you wish you can assume an upper limit of 20 cities, "named"
    54. 0-19, for this version of the program. You may also assume that the
    55. "names" of the nodes will be consecutive integers starting at 1.

    56. So, here is what the input file might look like for our problem including
    57. Dallas, Los Angeles, Boston and New York above.

    58. c 1
    59. c 2
    60. c 3
    61. c 4
    62. a 1 2 1400
    63. a 1 3 1950
    64. a 1 4 1900
    65. a 2 3 3150
    66. a 2 4 3100
    67. a 3 4 150

    68. Since we assume that the distance between cities X and Y is the same whether
    69. we go from X to Y or Y to X, we don't need to list the distance for each
    70. direction of travel between any pair of cities.

    71. Output:
    72. A single line which lists the nodes in a legal tour and the cost of that
    73. tour. So, for our the input file provided and the example tour listed above
    74. (New York, Dallas, Boston, Los Angeles New York) the actual output of your
    75. program might be:

    76. The tour 4 1 2 3 4 costs 7150.

    77. Also, remember that we will (attempt to) compile your program using the command

    78. gcc *.c

  2. #2
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    This doesn't seem too hard or time consuming, but it depends how much programming you have done before. You'll need to know how to handle command line arguments, and familiarity with arrays. If you're comfortable with those, it should only take you about an afternoon to do.
    Code:
    while(!asleep) {
       sheep++;
    }

  3. #3
    Registered User
    Join Date
    Jan 2013
    Location
    UK
    Posts
    19
    Haha, right I honest to god do peoples homework just because I believe they've tried.. but omg haha, go away

  4. #4
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    To be fair, the OP hasn't asked us to do it, just for an estimate of how hard it is.
    Code:
    while(!asleep) {
       sheep++;
    }

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Given that you only have to output "one legal tour", which the example is just the input order closed to make it a circuit, I'd say 30 mins to an hour.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,343
    You may want to spend a few hours reading up on the problem, and Dynamic programming.

    [edit]
    Did you know wiki has a page for this problem?
    [/edit]
    Fact - Beethoven wrote his first symphony in C

  7. #7
    Registered User
    Join Date
    Dec 2011
    Posts
    27
    Hey guys here is what I got for my program :
    Code:
    #include"stdio.h" int x[15],used[15]; int adj[15][15]={0}; int path[15][15],wght[15]; int c,min; int path_ok(int k,int n){ if(used[x[k]]) return 0; if(k‹n-1) return(adj[x[k-1]][x[k]]); else return(adj[x[k-1]][x[k]] && adj[x[k]][x[0]]); } void TSP(int k,int n) { int i,sum; for(x[k]=1;x[k]<n;x[k]++) { if(path_ok(k,n)) { used[x[k]]=1; if(k==n-1) { sum=0; printf("\n\n\tPOSSIBLE PATH %d : ",c+1); for(i=0;i<n;i++) { printf("%d\t",x[i]); path[c][i]=x[i]; sum+=adj[x[i]][x[i+1]]; } printf(" : %d",sum); wght[c]=sum; if(c==0 || sum<min) min=sum; c++; used[x[k]]=0;getch(); } else TSP(k+1,n); used[x[k]]=0; } } } void findmin(int n) { int i,j; for(i=0;i<c;i++) if(wght[i]==min) { printf("\n\n\tMINIMUM PATH : "); for(j=0;j<n;j++) printf("%d\t",path[i][j]); } } void main() { int i,n,j; int edg; clrscr(); printf("\n\n\t\tTRAVELLING SALESMAN PROBLEM\n\n"); printf("\n\tEnter the no. of Cities : "); scanf("%d",&n); printf("\n\n Enter the Cost if path Exist Between cities.:{c1,c2}.Else Enter 0\n\n"); printf("\n\tCITIES\t\tCOST\n\n"); for(i=0;i<n;i++) for(j=i+1;j<n;j++) { printf("\n\t %d------ %d \t:",i,j); scanf("%d",&edg); if(edg) adj[i][j]=adj[j][i]=edg; } used[0]=1; TSP(1,n); if(!c) printf("\n\n\t\tNO PATH FOUND TO COVER ALL THE CITIES\n\n"); else { printf("\n\n\t\tLEGAL TOUR IS %d AND THE PATHS ARE \n\n",min); findmin(n); } getch(); }
    Does anyone know what is wrong in this code?
    Last edited by return0; 02-15-2013 at 06:20 PM.

  8. #8
    Registered User
    Join Date
    Dec 2012
    Posts
    289
    HOLY CRAP!!!

    yeah i see a big prob, your entire formatting is jacked!

    edit/repost your code so we can read it, with proper indenting!

    thank you
    Salem likes this.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    Is that a program or poetry?
    Crossfire likes this.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Perhaps he was aiming at this?
    http://www.ioccc.org/1987/westley.c
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,214
    Perhaps he was aiming at this?
    Aiming a tad high aren't you?

    Soma

  12. #12
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    Quote Originally Posted by Salem View Post
    Perhaps he was aiming at this?
    http://www.ioccc.org/1987/westley.c
    I'm disappointed that that no longer compiles.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  13. #13
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Quote Originally Posted by King Mir View Post
    I'm disappointed that that no longer compiles.
    Consider it a challenge
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    Quote Originally Posted by Salem View Post
    Consider it a challenge
    There was only one line wrong. Easy to fix. C code - 47 lines - codepad. I'm happy now.

    Course that's still not c11...
    Last edited by King Mir; 02-16-2013 at 03:06 AM.
    Salem likes this.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #15
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,214
    O_o

    There is no need to order the operations as in the original so we can do a little better.

    Soma

    C code - 47 lines - codepad
    King Mir likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 12-10-2012, 11:25 PM
  2. Replies: 1
    Last Post: 03-03-2009, 03:47 PM
  3. Get program to copy itself into program files, then start on startup.
    By guitarist809 in forum Windows Programming
    Replies: 6
    Last Post: 03-03-2008, 08:42 AM
  4. Replies: 5
    Last Post: 08-16-2007, 11:43 PM
  5. Replies: 18
    Last Post: 11-13-2006, 12:11 PM

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