Like Tree2Likes
  • 2 Post By Nominal Animal

Very difficult task

This is a discussion on Very difficult task within the C Programming forums, part of the General Programming Boards category; So my teacher gave me the task to solve it for tomorrow but there is no possible way I can ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    7

    Very difficult task

    So my teacher gave me the task to solve it for tomorrow but there is no possible way I can do it

    So here it is:
    Along the circular road,there are N cities and in every city has it's own shop for appliances. You know (enter) the price of each fridge and the price of the trip (two-way ticket). For citizens of each city determinate the city in which they can find the cheapest fridge plus the smallest price for tickets. Directions can be clockwise or counterclockwise.

    Test example:

    Ticket: 4 3 4 10
    Fridge: 5 10 7 10

    For citizens of the first city: It's cheapest to go to the town 1.
    For citizens of the second city: It's best to stay in their own city
    For citizens of the the third city: It's best to stay in their own city
    For citizens of the fourth city: It's best to go the town 1.


    We came to arrays so no advanced techniques like pointers or functions are allowed.


    Thank you.

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    The rule is that you give it a shot first,try your attempt here and then the problem is sure to be solved.

  3. #3
    Registered User
    Join Date
    Sep 2012
    Posts
    7
    Oh didn't know that.


    Code:
    #include<stdio.h> 
    #include<conio.h> 
    #define MAX 40 
    
    
    int main() 
    { 
       int price[MAX],ticket[MAX],i,n,pos,xu,yu,s[MAX],j,z[MAX],q[MAX],min,t,pozk; 
       for(i=0;i<n;i++) cena[i]=karta[i]=0; 
       do 
       { 
          printf("Number of the city and fridges:");
          scanf("%d",&n); 
          if(n>0 && n<MAX) break; 
          clrscr(); 
       }            while(1); 
        printf("Enter the price of the fridges"); 
        xu=wherex(); 
        yu=wherey(); 
        xu=1; 
        yu++; 
       for(i=0;i<n;i++) 
       { 
         gotoxy(xu,yu); 
         scanf("%d",&price[i]); 
         xu+=5; 
         if(xu>80) xu=1,yu++; 
       } 
       printf("Entere the price of the tickets"); 
        xu=wherex(); 
        yu=wherey(); 
        xu=1; 
        yu++; 
       for(i=0;i<n;i++) 
       { 
          gotoxy(xu,yu); 
         scanf("%d",&ticket[i]); 
         xu+=5; 
         if(xu>80) xu=1,yu++; 
       } 
       printf("\n\nEnter the city where you are located:"); 
       do{ 
           xu=wherex(); 
           yu=wherey(); 
       scanf("%d",&poz); 
       if(poz>0 && poz<n) break; 
       gotoxy(xu,yu); 
       printf("         "); 
       gotoxy(xu,yu); 
       }while(1); 
       s[0]=min; 
       for(i=0;i<n;i++) 
       { 
            s[i]=ticket[i]+price[i]; 
            if(s[i]<min) min=s[i],pozk=j; 
    
    
       } 
       printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]); 
       getch(); 
    }
    The problem with my code is that it's showing only the place where the cheapest ticket and price of the fridge are.

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The code you've posted doesn't compile.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Registered User
    Join Date
    Sep 2012
    Posts
    7
    Code:
    #include<stdio.h>
    #define MAX 40
    
    
    
    
    int main()
    {
       int price[MAX],ticket[MAX],i,n,loc,xu,yu,s[MAX],j,z[MAX],q[MAX],min,t,pozk;
       for(i=0;i<n;i++) price[i]=ticket[i]=0;
       do
       {
          printf("Number of the city and fridges:");
          scanf("%d",&n);
          if(n>0 && n<MAX) break;
          printf("Wrong entry!!!");
       }            while(1);
        printf("Enter the price of the fridges\n");
       for(i=0;i<n;i++)
       {
         printf("Fridge No[%d]:",i+1);
         scanf("%d",&price[i]);
       }
       printf("Entere the price of the tickets\n");
       for(i=0;i<n;i++)
       {
         printf("Ticket for city number[%d]:",i+1);
         scanf("%d",&ticket[i]);
    
    
       }
       printf("\n\nEnter the city where you are located:");
       do{
       scanf("%d",&loc);
       if(loc>0 && loc<n) break;
       printf("Wrong entry!!!");
       }while(1);
       s[0]=min;
       for(i=0;i<n;i++)
       {
            s[i]=ticket[i]+price[i];
            if(s[i]<min) min=s[i],pozk=j;
    
    
    
    
       }
       printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]);
    
    
    }
    Here is the version w/out getch(); and other conio.h-related functions.

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Code:
    #include<stdio.h>
    
    #define MAX 40
    
    int main(void)
    {
       int price[MAX],ticket[MAX],i,n,loc,xu,yu,s[MAX],j,z[MAX],q[MAX],min,t,pozk;
       /// t, q, z, yu, and xu are not used !!!
    
       for(i=0;i<n;i++) price[i]=ticket[i]=0;   /// n has no value !!!
    
       while (1)
       {
          printf("Number of the city and fridges:");
          scanf("%d",&n);
          if(n>0 && n<MAX) break;
          printf("Wrong entry!!!");
       }
    
       printf("Enter the price of the fridges\n");
    
       for(i=0;i<n;i++)
       {
         printf("Fridge No[%d]:",i+1);
         scanf("%d",&price[i]);
       }
    
       printf("Enter the price of the tickets\n");
    
       for(i=0;i<n;i++)
       {
         printf("Ticket for city number[%d]:",i+1);
         scanf("%d",&ticket[i]);
       }
    
       printf("\n\nEnter the city where you are located:");
    
       while (1)
       {
          scanf("%d",&loc);
          if(loc>0 && loc<n) break;
          printf("Wrong entry!!!");
       }
    
       s[0]=min;   /// min has no value !!!
    
       for(i=0;i<n;i++)
       {
            s[i]=ticket[i]+price[i];
            if(s[i]<min) min=s[i],pozk=j;  /// j has no value !!!
       }
    
       printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]);
    
       return 0;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Registered User
    Join Date
    Sep 2012
    Posts
    7
    Code:
    #include<stdio.h>
    
    
    #define MAX 40
    
    
    int main(void)
    {
       int price[MAX],ticket[MAX],i,n,loc,s[MAX],j,min,pozk;
    
    
    
    
       for(i=0;i<MAX;i++) price[i]=ticket[i]=0;
       while (1)
       {
          printf("Number of the city and fridges:");
          scanf("%d",&n);
          if(n>0 && n<MAX) break;
          printf("Wrong entry!!!");
       }
    
    
       printf("Enter the price of the fridges\n");
    
    
       for(i=0;i<n;i++)
       {
         printf("Fridge No[%d]:",i+1);
         scanf("%d",&price[i]);
       }
    
    
       printf("Enter the price of the tickets\n");
    
    
       for(i=0;i<n;i++)
       {
         printf("Ticket for city number[%d]:",i+1);
         scanf("%d",&ticket[i]);
       }
    
    
       printf("\n\nEnter the city where you are located:");
    
    
       while (1)
       {
          scanf("%d",&loc);
          if(loc>0 && loc<n) break;
          printf("Wrong entry!!!");
       }
    
    
       min=s[0];
    
    
    
    
       for(i=0;i<n;i++)
       {
            s[i]=ticket[i]+price[i];
            if(s[i]<min) min=s[i],j=pozk;
       }
    
    
       printf("Ticket:%d\n Price of the fridge:%d ",ticket[pozk],price[pozk]);
    
    
       return 0;
    }

    Okay but the logic in my task is wrong so someone needs to give me the direction to solve this problem.

  8. #8
    Registered User ledow's Avatar
    Join Date
    Dec 2011
    Posts
    435
    What's the value of s[0] when you do min = s[0]?

    What's the value of pozk when you do j = pozk (conditionally, so only SOMETIMES) and then later print it?

    What is the loop at the end supposed to be doing (looks like it finds the smallest journey only, not the smallest for each town)?

    Why do you only print one line after the loop? (i.e. where's your result).

    What you've done is put the code for the bits you know how to do (and which mainly consists of inputting numbers) and then gone "Huh?!" and expected everyone else to fill in the gaps. The entire point of the exercise is for you to work out what goes there.

    If you're struggling, read through your code as if it were English (or you native language). That's how you formulate your algorithms, that's how you work out what code does, that's how you spot your errors. At the moment, your last for loop does this:

    Code:
    For each of your array's elements
    {
      Store the total price in another array.
      If the total price is less than the minimum, make the minimum the total price and make j the same as pozk.
    }
    If your first questions aren't: what's the minimum, what's j, what's pozk, what are their values before we begin, what are they trying to hold, what do we do with this "other array"?
    then you probably haven't bothered to read through the code yourself, and have just slapped something together to look convincing.

    - Compiler warnings are like "Bridge Out Ahead" warnings. DON'T just ignore them.
    - A compiler error is something SO stupid that the compiler genuinely can't carry on with its job. A compiler warning is the compiler saying "Well, that's bloody stupid but if you WANT to ignore me..." and carrying on.
    - The best debugging tool in the world is a bunch of printf()'s for everything important around the bits you think might be wrong.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    It's quite late to tackle a puzzle, but this looks doable.

    Our cities are laid out, from left to right:
    Code:
    City:   1  2  3  4
    ======================
    Ticket: 4  3  4 10
    Fridge: 5 10  7 10
    And let's say we're moving from left to right, and after City #4, we loop back to City #1, so it's a circular, but one way travel direction.

    The cost for each city's citizens would be:
    Code:
        Fridge    Tickets   Total
    ==================================================
    1)    5     +   0        5       Stay in City 1
    1)   10    +   4         14       Go to City 2
    1)    7     +  4+3       14       Go to City 3
    1)    10   +  4+3+4      21       Go to City 4
    -------------------------------------------------
    2)   10    +   0         10       Stay in City 2
    2)    7     +  3         10       Go to City 3
    2)   10    +  3+4        17       Go to City 4
    2)    5     + 3+4+10     22       Go to City 1
    Does that look like what you need to do, (in some format), to solve this?

    When the cost of the venture being considered exceeds the cost of the lowest one already calculated, there's no need to continue, but run time will be inconsequential (very fast), anyway.

    So what about organizing the data into rows. One row for each city, row 1 is city 1, row 2 is city 2 data, etc.? Row 0 is left blank.

    Then columns can be 0 for the tickets, and 1 for the fridge cost of that city, in each row. column 11 (row 1), could hold the total cost for city 1, column 12 could hold he total cost for going to city 2 (so it's 10 + the city number where you're going, see?).

    Row 2 would be the same, with column 11 (row 2) holding the total cost for going to city 1 and buy the fridge there, column 12 holding the total cost to go to city 2 and buy the fridge, etc.

    The answer would be the lowest of columns 11 through column 14, in the row of the city in question.

    Sound reasonable?
    Last edited by Adak; 09-27-2012 at 03:24 AM.

  10. #10
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Assuming the inputs are interpreted as
    Code:
        City     (4)    1     2     3      4
        Ticket       4     3     4     10 
        Fridge          5    10     7     10
    it is easy to construct the logic needed to find the cheapest (and let's say "fastest" -- break ties by choosing the least number of tickets needed) way to buy a fridge. However, the results are different:
    Code:
        In city 1, it is cheapest to buy a fridge locally for 5.
        In city 2, it is cheapest to buy a fridge from city 1, for 5 + 3 = 8.
        In city 3, it is cheapest to buy a fridge locally for 7.
        In city 4, it is cheapest to buy a fridge from city 1, for 5 + 4 = 9.
    One could also interpret the data as
    Code:
        City     1     2     3     4    (1)
        Ticket      4     3     4     10 
        Fridge   5    10     7    10
    
        In city 1, it is cheapest to buy a fridge locally for 5.
        In city 2, it is cheapest to buy a fridge from city 1 for 5 + 4 = 9.
        In city 3, it is cheapest to buy a fridge locally for 7.
        In city 4, it is cheapest to buy a fridge locally for 10.
    Start at the current city, and the fridge price there. This is the initial best price.

    Next, do a loop with two imaginary travellers, one going clockwise, the other counterclockwise. Each traveller at each stop (city) compares the fridge price at that city plus the accumulated ticket costs, to the best price. If it is better than the currently best price, update the best price (and the city it was obtained from, and optionally which way the traveller went). Repeat until both travellers have arrived back at the original city.

    To find the optimum for all cities, you simply repeat the above loop for each city separately. (You could also use a separate pair of virtual travellers for each city; that solution becomes useful only when you have lots of cities, and wish to parallelize the work using multiple threads. In this particular problem it is not useful at all, because there is not enough work to do at each stop.)

    Tip 1: Note that there are two prices to reach any given city from any given city: one clockwise, and the other counterclockwise. If you use < for the best price comparison, among multiple equal prices you'll get the one with the fewest trips, because those are found earlier in the loop. If you use <= you'll get the one with the most trips, since later iterations will be preferred over earlier ones for equal price.

    Tip 2: Your loop does need to go fully around, both travellers to the origin city (actually, the city before that). It is not enough to go half way, i.e. when the travellers meet! Consider a case where almost all trips are almost free, with the cheapest fridge at the next city clockwise, but that one trip being very expensive. The cheapest way might just be to travel almost the entire circuit counterclockwise to the city next clockwise! While this does not happen with these exact inputs, you shouldn't assume it will never happen.
    Adak and kantagara like this.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Great discussion by Nominal Animal ^^^. Especially good was the part about the need to check which way is the better way to move, to get the best price (clockwise or counter clockwise), and the need to go all the way around.

  12. #12
    Registered User
    Join Date
    Sep 2012
    Posts
    7
    Thank you Nominal Animal...I will try something with your help...
    Now I have some other problem with some other task...

    How can I randomize numbers from one to seven in one array without repeating?
    Code:
     
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 7
    int main()
    {
        int x[MAX],i,j;
        for(i=0;i<MAX;i++) x[i]=0;
        for(i=0;i<MAX;i++)
        {
            j=0;
            randomize();
            x[i]=random(7);
            while(j<i){ j++; if(x[i]==x[j]) break;}
            if(j!=i) while(x[j]!=x[i]) x[i]=random(7);
        }
        for(i=0;i<MAX;i++)
        {
            printf("%d\n",x[i]);
        }
    }
    I tried like this,but it gets me the same number over and over

  13. #13
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    383
    Quote Originally Posted by kantagara View Post
    Thank you Nominal Animal...I will try something with your help...
    Now I have some other problem with some other task...

    How can I randomize numbers from one to seven in one array without repeating?
    Code:
     
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 7
    int main()
    {
        int x[MAX],i,j;
        for(i=0;i<MAX;i++) x[i]=0;
        for(i=0;i<MAX;i++)
        {
            j=0;
            randomize();
            x[i]=random(7);
            while(j<i){ j++; if(x[i]==x[j]) break;}
            if(j!=i) while(x[j]!=x[i]) x[i]=random(7);
        }
        for(i=0;i<MAX;i++)
        {
            printf("%d\n",x[i]);
        }
    }
    I tried like this,but it gets me the same number over and over
    What does the "randomize" function do? It's not a standard function.

    My guess is it's a Terrible C extension which sets the seed from the current time. If that's the case, you're likely seeding the random-number generator with the same initial random number every time through the loop, since the system clock doesn't change during the loop. Call randomize() only once in your program, such as at the top of main().

    But for the task at hand (generating an array of non-repeating random numbers), this could be called "shuffling". Set each element to its index plus one (x[0] = 1, x[1] = 2, etc), iterate through each element in the array except for the last, and then swap the value at that index and one of the remaining elements (from a randomly chosen index, of course). This might have an off-by-one error (I haven't tested it), but the basic concept should work for shuffling the values.

  14. #14
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Quote Originally Posted by christop View Post
    this could be called "shuffling".
    It is. The common method is well described in the Wikipedia article for Fisher-Yates shuffle (also known as Knuth shuffle).

    The basic idea is to first create an array with all the values, then either reorder them by swapping each one with a random one in the array, or by creating a copy of the array where the elements are in random order. Remember that in C, arrays are zero based, i.e. a[0] is the first element.

    There are algorithms for filling an array with consecutive numbers in random order, but they are very tricky to write right. Most implementations suffer from subtle bugs that cause the order to be less random than expected (nonuniform distribution). First filling an array and then shuffling it is much simpler and much more robust.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How Difficult is This?
    By MAtkins in forum C Programming
    Replies: 43
    Last Post: 02-11-2011, 01:21 PM
  2. Replies: 2
    Last Post: 12-31-2007, 10:40 AM
  3. A difficult Question for me
    By SuperNewbie in forum Windows Programming
    Replies: 3
    Last Post: 11-06-2003, 05:11 AM
  4. A difficult Problem.
    By Kam in forum C Programming
    Replies: 4
    Last Post: 11-13-2002, 04:06 AM
  5. why must everything be so difficult!
    By ... in forum C++ Programming
    Replies: 14
    Last Post: 03-22-2002, 03:21 PM

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