1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Help!!

Discussion in 'C' started by Levi, Sep 15, 2004.

  1. Levi

    Levi New Member

    Joined:
    Aug 21, 2004
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    Hey everyone,
    I am having big problems with three problems. The programs are quicksort.c, fill.c, and removedup.c. Can you give me any help. Thanks so much. Here are the instructions.
    Levi


    Quicksort.c

    Write a program that implements the quicksort algorithm. Quicksort is a popular sorting
    algorithm, developed by the British Computer Scientist Tony Haore.
    Your input consists of a list of words and the output should display the same list but sorted.
    For example, if the input is:
    Russian English Italian Spanish Hebrew French German
    the output will be:
    English French German Hebrew Italian Russian Spanish
    The method of quicksort works in the following way; For the input array,
    25 50 48 37 10 92 87 33
    we will need to follow these steps:
    1. We first choose one element from the input numbers which serves as the boundary between
    the small and large elements. This element is called the pivot. You can choose any element
    for this purpose, and the simplest way is to select the first element in the array, namely 25 in
    this example will be the current pivot.
    2. At the next stage, we rearrange the elements of the array so that large elements are moved to
    the end of the array and small elements toward the beginning. By the end of this stage we’ll
    get the following array,
    10 25 50 48 37 92 87 33
    elements pivot elements larger than 25
    less than 25
    Note that 25 is now positioned in its right location.
    By the end of this stage we got two sub arrays,
    [10] and [5048 37 92 87 33] that need to be treated at the same way.
    3. At the next stage we sort the elements of each of the sub arrays. Because all elements to the
    left of the pivot boundary are strictly less than all those to the right, sorting each of the sub
    arrays must leave the entire array in sorted order. These sub arrays can be sorted using a
    recursive application of quicksort.
    For the sub array [10] we do not need to do anything since it contains only one element. So
    we need to repeat this process only for the sub array [50 48 37 92 87 33].
    4. The current pivot now is 50 (since this is the first element of the current sub array.)
    Once again we rearrange the elements of this sub array so that the large elements are moved
    toward the end of the sub array and small elements towrd the beginning as follows,
    10 25 [48 37 33] 50 [92 87]
    This process will be repeated for the two new sub arrays that were created, and so forth until all
    the array is sorted.
    c11b - Programming Exercises - 37 -
    As a whole, the passes for this input can be described in the following way,
    input: 25 50 48 37 10 92 87 33
    stage 1: [10] 25 [50 48 37 92 87 33]
    pivot
    stage 2: 10 25 [50 48 37 92 87 33]
    stage 3: 10 25 [48 37 33] 50 [92 87]
    pivot
    stage 4: 10 25 [37 33] 48 50 [92 87]
    pivot
    stage 5: 10 25 [33] 37 48 50 [92 87]
    pivot
    stage 6: 10 25 33 37 48 50 [92 87]
    stage 7: 10 25 33 37 48 50 [87] 92
    pivot
    stage 8: 10 25 33 37 48 50 87 92
    Try to implement this algorithm in a recursive way. Run your program on any input you wish of
    size >= 20.


    Fill.c

    Write a program that gets as an input:
    • A perimeter (boundary) of a “closed” shape, such as an ellipse, circle, etc,.
    • Coordinates of an interior point.
    The program should fill in a recursive way the area (enclosed by) this shape from the given
    interior point without exceeding the boundary of this shape. For example if the input:
    ***** *****
    * * *****
    * * then the output will be: *****
    * * *****
    ***** *****
    Instructions
    The input will include:
    • m lines, each including n characters. If the character read is not a space, the character belongs
    to the boundary of the shape.
    • Two numbers that specify the coordinates, namely the row and column indices of the point
    from which the program is supposed to start filling the shape.
    You can assume that this input point is inside the shape and that the shape is really closed. The
    interior point is such that to any direction you “go” from this point, you will eventually reach the
    boundary.
    Note that the perimeter is represented as a sequence of characters (asterisks).
    The program should display both the shapes before filling the shape and after filling the shape.
    For example, for the following shape and point,
    ***** *****
    * * * * point in location [3,6]
    * *** *
    * *
    * *
    *************
    the input will consist of:
    1. Six lines as follows,
    ***** *****
    * * * *
    * *** *
    * *
    * *
    *************
    2. The pair (3 , 6)
    c11b - Programming Exercises - 39 -
    Run your program on the following shapes,
    Rectangle:
    **********
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    **********
    Ellipse:
    ******
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * *
    * * ******
    The letter “H”:
    *** ***
    * * * *
    * * * *
    * * * *
    * ****** *
    * *
    * ****** *
    * * * *
    * * * *
    * * * *
    * * * *
    *** ***
    Hints
    1.The recursive procedure, fill, should be very short..
    The procedure, fill, takes three arguments: Row and column of the current point checked and the
    multidimensional array that represents the shape.
    2. Think of a simple end condition, and of the neighbouring cells.

    Removedup.c

    Write a program that removes all duplicate values from a sorted array of integers, leaving only a
    single copy of each value. For example if the input array is inpArray with the following values,
    InpArray
    50 60 70 70 72 80 85 85 90 100
    then the output array will be,
    OutArray
    50 60 70 72 80 85 90 100
    Your program should include a function named removedup that returns the new size of the array
    (without the duplicates). For this input array,
    removedup (inpArray, inpArraySize, outArray) 8
    In addition, your program should display both the input array and the output array.
    File name should be, removeD.c
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    Code:
    void quicksort(int *a,int left,int right)
    {
     int temp,l,r,pivot;
     int i;
     l=left;
     r=right;
     pivot=a[(left+right)/2];
     do
     {
      while(a[l]<pivot)
       l++;
      while(a[r]>pivot)
       r--;
      if(l<=r)
      {
        temp=a[l];
        a[l++]=a[r];
        a[r--]=temp;
      }
     }while(l<=r);
     if(left<r)
      quicksort(a,left,r);
     if(l<right)
      quicksort(a,l,right);
    }
    
    code to implement Quick Sort in a recursive way
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    I have choosen the middle one
    Code:
    pivot=a[(left+right)/2];
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    Code:
    int RemoveDup(int inpArr[],int size, int outArr[])
    {
    	int i,j;
    	for(i=0,j=0;i<size;i++)
    	{
    		if(i==0)
    		{
    			outArr[j++] = inpArr[i];
    			continue;
    		}
    		if(inpArr[i]!=inpArr[i+1])
    			outArr[j++] = inpArr[i];
    	}
    	return j;
    }
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    Regarding your Fill I could not get what you meant and the input and output stuffs. Try to be more clear if possible.

    Also please make your titles and other stuffs more clear and try reading [thread=168]this thread[/thread].
     
  6. Levi

    Levi New Member

    Joined:
    Aug 21, 2004
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    Hey,
    Thanks for all your help. I'll try it and tell you how it goes.
    Levi
     
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    My Pleasure
    I will wait for that.

    Thanks
    Shabbir Bhimani
     
  8. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    hey...I'm a new user and i can see that u are also doing the programming course through EPGY? or no...i have similar prgms and also need help with the fill.c prgm. The prgm takes a square of astersiks and a midpoint that lays inside the square and u need the fill function to print the same square but where the inside is filled with astersiks as well as the boundary.
    -Blaze
     
  9. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    to view his pictures copy his asterisk pictures then paste them in a reply box or when u are making a message like the one i am making right now... and to add to my last message...u also have to b able to run the prgm on cirlces, squares, the letter H and many other funky shapes. Thank you
    -Blaze
     
  10. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    nvm bout the copy past thing... dont work.. here ya go:
    input = ***** *****
    * mid* then output: *****
    ***** *****

    must b able to work on Rectangle:
    ********
    * *
    * *
    * *
    ********

    Ellipse:
    *****
    ** **
    * *
    * *
    * *
    * *
    * *
    ** **
    *****


    The letter H:
    *** ***
    * * * *
    * * * *
    * **** *
    * *
    * **** *
    * * * *
    * * * *
    *** ***

    I EDITED THIS MESSAGE...IT DOESNT WORK...A CORRECTED VERSION IS ON THE NEXT PAGE PLZ VISIT
    Thanks
    -Blaze
     
    Last edited: Dec 31, 2004
  11. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    ok...this is really buggin me...the website automatically takes out the spaces
    im gonna put 0's where the spaces shud b
    HERE YA GO (better work)
    input =
    *****
    *000*
    *000*
    *000*
    *****
    then output:
    *****
    *****
    *****
    *****
    *****


    must b able to work on Rectangle:
    ********
    *0000000*
    *0000000*
    *0000000*
    ********

    Ellipse:
    000*****
    0**00000**
    *000000000*
    *000000000*
    *000000000*
    *000000000*
    *000000000*
    0**00000**
    000*****


    The letter H:
    ***0000***
    *0*0000*0*
    *0*0000*0*
    *0******0*
    *000000000*
    *0******0*
    *0*00000*0*
    *0*00000*0*
    ***00000***

    BETTER WORK OR I GIVE UP
    Thanks
    -Blaze
     
  12. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    to make it look better just take out the 0's and put spaces in... Remember only the asterisks are the boundaries
    Thanks
    -Blaze
     
  13. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    please reply soon i need this program ASAP
    thnx for all your help
    -blaze
     
  14. alok

    alok New Member

    Joined:
    Jul 24, 2004
    Messages:
    127
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    S/W Engg
    Home Page:
    Have tried your self yet Mr Blaze.
    just try and then post your Source COde here,then we can help.
    NO body going to write full source Code for you HERE!!
     
  15. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    heres what i have so far...i think this is the right logic but sum numbers are screwy or sumthing


    /* fill.c is a program that takes an input of a boundary and
    * the coordinates of an interior point. The program then takes
    * those and dispays the boundary but as a closed shape. It
    * fills the shape.
    */

    #include "stdafx.h"
    #include "simpio.h"
    #include "strlib.h"

    void fill(int Row, int Column, char Shape[21][21]);
    void GO(int Row, int Column, char Shape[21][21]);

    main(int count, int Count , int Sentinel, char Temp, int Row, int Column, string check)
    {
    char Shape[21][21];
    for(count = 0; count < 21; count++) {
    for(Count = 0; Count < 21; Count++) {
    Shape[count][Count] = ' ';
    }
    }
    Sentinel = 0;
    printf("Start Entering Your Shape One Character At A Time And Enter [0] when done \n");
    printf("Only 20 Rows & Columns Max \n");
    for(Count = 0; Sentinel != 1; count++) {
    for(count = 0; Sentinel != 1; count++) {
    Temp = getchar();
    if(Temp == '0') {
    Sentinel = 1;
    }
    Shape[Count][count] = Temp;
    }
    }
    check = GetLine();
    printf("\nNow Enter The Row of the inner coordinate \n");
    Row = (GetInteger() - 1);
    printf("Now Enter The Column of the inner coordinate \n");
    Column = (GetInteger() - 1);
    fill(0, 0, Shape);
    printf("\n");
    }

    void fill(int Row, int Column, char Shape[21][21])
    {
    if(Shape[Row][Column] != ' ' && Shape[Row][Column] != '0') {
    printf("*");
    } else {
    GO(Row, Column, Shape);
    }
    if(Column == 20 && Row < 20) {
    printf("\n");
    fill(Row + 1, 0, Shape);
    }
    else if(Row < 20 && Column < 20) {
    fill(Row, Column + 1, Shape);
    }
    }

    void GO(int Row, int Column, char Shape[21][21])
    {
    int check = 0;
    for(int count = Row; count >= 0; count = count - 1) {
    if(Shape[count][Column] != ' ' && Shape[count][Column] != '0') {
    check = check + 1;
    count = 0;
    }
    }
    for(int count = Row; count <= 20; count++) {
    if(Shape[count][Column] != ' ' && Shape[count][Column] != '0') {
    check = check + 1;
    count = 20;
    }
    }
    for(int count = Column; count >= 0; count = count - 1) {
    if(Shape[Row][count] != ' ' && Shape[Row][count] != '0') {
    check = check + 1;
    count = 0;
    }
    }
    for(int count = Column; count <= 20; count++) {
    if(Shape[Row][count] != ' ' && Shape[Row][count] != '0') {
    check = check + 1;
    count = 20;
    }
    }
    if(check == 4) {
    printf("*");
    } else {
    printf(" ");
    }
    }
     
  16. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    Instead of posting the complete code if you can lay us the problem are we can help or you can use http://www.globaldevelopers.net/ and some software developer will do it for you also.
     
    Last edited: Jan 3, 2005
  17. BlazeB

    BlazeB New Member

    Joined:
    Dec 31, 2004
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    the problem is, I can't get the program to function correctly but i dont know where the prob is...btw alok, the user that posted b4 u told me to post my source code. If you want to know what the prgm is supposed to do then read the first descriptions and look at my pictures (it's the fill.c prgm)
    -Blaze
     
  18. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    Likes Received:
    364
    Trophy Points:
    83
    Yes I have read that and also if you have read this thread I have helped the guy who has started. Seeing the program and running is a difficult task but if you can recognize the problem are you can use this forums or you can use our partner sites for the work also.
     
  19. Levi

    Levi New Member

    Joined:
    Aug 21, 2004
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    Hey,
    I am taking a course through epgy. Write what you have of the program
    so far, and I'll see how I can help. Sorry for not responding sooner.
    Levi
     
  20. Levi

    Levi New Member

    Joined:
    Aug 21, 2004
    Messages:
    30
    Likes Received:
    0
    Trophy Points:
    0
    Hey,
    I'm going to post the code for the fill.c program. I'm assuming that you have not completed it right? Use the code as a helper, don't just copy and paste. See if you can understand what is going on in there, and if you don't write back and ask your questions.
    Of course, the fill function is the heart of the program. The Square, Circle and H, functions just make it easier to use the program. I found it near impossible to make it easy to imput a shape, so I wrote those. It's nice to know that there is someone else out there taking a programming course with EPGY. :)
    Levi



    /*
    * This program fills in a recursive way the area enclosed
    * by a shape from a given interior point without exeeding
    * the boundary of the shape.
    */



    #include <stdio.h>
    #include "genlib.h"
    #include "simpio.h"
    #include "strlib.h"
    #include "conio.h"
    #define height 15
    #define width 12


    string shape[height][width];
    void getinput(string shape[height][width]);
    void printshape(string shape[height][width]);
    void fill(string shape[height][width],int x, int y);
    void square(string shape[height][width]);
    void circle(string shape[height][width]);
    void H(string shape[height][width]);
    void prntsquare(string shape[height][width]);
    main()
    {
    int x, y,ans;
    printf("This program fills in a recursive way the area enclosed\nby a shape from a given interior point without exeeding\nthe boundary of the shape.\n");
    printf("\n\nDo you want to see a \n1)square\n2)circle\n3)the letter H\n4)input yourself?\n");
    printf("Type the number to make your selection....for example,\nfor square,enter number 1\n");
    ans=GetInteger();
    switch(ans)
    {
    case 1: square(shape);break;
    case 2: circle(shape);break;
    case 3: H(shape);break;
    case 4: getinput(shape);break;
    }
    printf("Enter a x start position that is not an astrick.");
    x=GetInteger();
    printf("Enter a y start position that is not an astrick.");
    y=GetInteger();
    printshape(shape);
    fill(shape,x,y);
    printshape(shape);
    }
    void H(string shape[height][width])
    {
    int u,i;
    clrscr();
    for(u=0;u<height;u++)
    {
    for(i=0;i<width;i++)
    {
    shape=" ";
    }
    }
    for(u=0;u<=11;u++)
    {
    shape[0]="*";
    shape[9]="*";
    }
    for(i=0;i<=9;i++)
    {
    if((((((i==0||i==1||i==2||i==7||i==8||i==9))))))
    {
    shape[0]="*";
    shape[11]="*";
    }
    else
    {
    shape[4]="*";
    shape[6]="*";
    }
    }
    shape[4][2]="*";
    shape[4][7]="*";
    shape[6][2]="*";
    shape[6][7]="*";
    for(u=1;u<4;u++)
    {
    shape[2]="*";
    shape[7]="*";
    }
    for(u=7;u<11;u++)
    {
    shape[2]="*";
    shape[7]="*";
    }
    }
    void circle(string shape[height][width])
    {
    int n, n1;
    for(n=0;n<height;n++)
    {
    for(n1=0;n1<width;n1++)
    {
    shape[n][n1]=" ";
    }
    }
    for(n=3;n<(width-3);n++)
    {
    shape[0][n]="*";
    shape[14][n]="*";
    }
    for(n1=3;n1<12;n1++)
    {
    shape[n1][0]="*";
    shape[n1][11]="*";
    }
    shape[1][2]="*";
    shape[1][9]="*";
    shape[2][1]="*";
    shape[2][10]="*";
    shape[12][1]="*";
    shape[12][10]="*";
    shape[13][2]="*";
    shape[13][9]="*";
    }


    void square(string shape[height][width])
    {
    clrscr();
    prntsquare(shape);
    printf("\n\nEnter a co-ordinate inside the square");
    }

    void prntsquare(string shape[height][width])
    {
    int a,b;
    for(a=0;a<height;a++)
    {
    for(b=0;b<width;b++)
    {
    shape[a]=" ";
    }
    }


    for(a=0;a<9;a++)
    {
    shape[0][a]="*";
    shape[11][a]="*";
    }
    for(b=0;b<12;b++)
    {
    shape[0]="*";
    shape[9]="*";
    }

    for (a=0;a<height;a++)
    {
    for(b=0;b<width;b++)
    {
    printf("%s",shape[a]);
    }
    printf("\n");
    }
    }

    void getinput(string shape[height][width])
    {
    int col, row,var;
    var=0;
    clrscr();

    for(row=0;row<height;row++)
    {
    for(col=0;col<width;col++)
    {
    shape[row][col]=" ";
    }
    }
    printf("The maximum limits for the shape is %d from top to bottom,\nand %d from left to right.\n",height,width);
    printf("Enter your shape from left to right, top to bottom.\n");
    printf("Each time you enter a astrick, the shape will print,\nshowing you what you have inputed sofar.");
    printf("Enter \"-1\", to signal that you are done inputing.");
    for(row=0;row<height;row++)
    {
    for(col=0;col<width;col++)
    {
    shape[row][col]=GetLine();
    printf("\n");
    if(StringEqual(shape[row][col],""))shape[row][col]=" ";
    if(StringEqual(shape[row][col],"-1"))
    {
    shape[row][col]=" ";
    printshape(shape);
    var=-1;
    break;
    }
    printshape(shape);
    }
    if(var==-1)
    {
    break;
    }
    printf("New line.");
    }
    }


    void printshape(string shape[height][width])
    {
    int r,c;
    for (r=0;r<height;r++)
    {
    for(c=0;c<width;c++)
    {
    printf("%s",shape[r][c]);
    }
    printf("\n");
    }
    printf("\n");
    }


    void fill(string shape[height][width],int x,int y)
    {
    if(StringEqual(shape[x][y],"*")==FALSE)
    {
    shape[x][y]="*";
    fill(shape,x+1,y);
    fill(shape,x-1,y);
    fill(shape,x,y+1);
    fill(shape,x,y-1);
    }
    }
     

Share This Page