Like Tree1Likes
  • 1 Post By cyberfish

Find the fixed point of an array ...i.e return i if a[i]=i..

This is a discussion on Find the fixed point of an array ...i.e return i if a[i]=i.. within the C Programming forums, part of the General Programming Boards category; Write a c program for the following Find the fixed point of an array ...i.e return i if a[i]=i.. OBJECTIVE: ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    2

    Question Find the fixed point of an array ...i.e return i if a[i]=i..

    Write a c program for the following

    Find the fixed point of an array ...i.e return i if a[i]=i..


    OBJECTIVE: Find the "fixed point" of an array

    Input: an array A of *distinct* integers in ascending order.

    (Remember that integers can be negative!) The number of

    integers in A is n.
    Output: one position i in the list, such that A[i]=i, if any exists.

    Otherwise: "No".

    method 1 :
    If A [ i ] > i , we can ignore the right half of the array because

    in right half ,for all j > i , we must have A [ j ] > j since A [ i ] >

    i, as all the numbers are distinct.
    Similarly , if A [ i ] < i, we can ignore the left half of the array

    because in left half, for all j < i , we must have A [ j ] < j since A

    [ i ] < i ,as all the numbers are distinct.

    method 2:
    n = size of array
    take it=n/2

    iterate till it>0&&it<n
    if(A[it]>it)
    it=it/2
    else if(A[it]<it)
    it+=it/2
    else
    return it

    if loop returns nothing return error msg

    I have tried to write the following code...but got infinite loop error
    #includ
    Code:
    e<stdio.h>
    #include<math.h>
    main()
    {
     int a[20];
    int n,i,mid,low,high,j,temp;
    
     printf("\nEnter the Limit          : ");
     scanf("%d",&n);
     printf("\nEnter the numbers        : ");
     for(i=0;i<n;i++)
       scanf("%d",&a[i]);
     
     low=0;
         high=n-1;
       do
         {
          mid= (low + high) / 2;
         
      if(a[mid]==mid )
    {
    
                   printf("Present = %d \n",a[mid]);                 
    }
    
    
          
           
           else if(a[mid]< mid)
                 low = mid + 1;
    
        
        else  high = mid - 1;
    continue;
        
            } while( low <= high);
    }

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    Are you trying to be artistic with the indentation?

    You'll want to fix the indentation if you want anyone to read your code.
    Libpgeak likes this.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    2
    Sorry for that mistake.
    I have re posted the code in a more readable form
    Code:
    #include<stdio.h>
    
    #include<math.h>
    main()
    
    {
     int a[20];
     int n,i,mid,low,high;
    
     printf("\nEnter the Limit          : ");
     scanf("%d",&n);
     printf("\nEnter the numbers        : ");
    
    
    
     for(i=0;i<n;i++)
    
     scanf("%d",&a[i]); 
    
     low=0;
    
     high=n-1;
    
       do
    
         {
    
          mid= (low + high) / 2;
    
          
    
          if(a[mid]==mid )
    
            {
    
              printf("Present = %d \n",a[mid]);                 
    
            }
    
           else if(a[mid]< mid)
    
                 low = mid + 1;
    
           else  high = mid - 1;
    
        continue;
    
      } while( low <= high);
    
    }
    Write a c program for the following

    Find the fixed point of an array ...i.e return i if a[i]=i..


    OBJECTIVE: Find the "fixed point" of an array

    Input: an array A of *distinct* integers in ascending order.

    (Remember that integers can be negative!) The number of

    integers in A is n.
    Output: one position i in the list, such that A[i]=i, if any exists.

    Otherwise: "No".

    method 1 :
    If A [ i ] > i , we can ignore the right half of the array because

    in right half ,for all j > i , we must have A [ j ] > j since A [ i ] >

    i, as all the numbers are distinct.
    Similarly , if A [ i ] < i, we can ignore the left half of the array

    because in left half, for all j < i , we must have A [ j ] < j since A

    [ i ] < i ,as all the numbers are distinct.

    method 2:
    n = size of array
    take it=n/2

    iterate till it>0&&it<n
    if(A[it]>it)
    it=it/2
    else if(A[it]<it)
    it+=it/2
    else
    return it

    if loop returns nothing return error msg

    I have tried to write the following code...but got infinite loop error
    Last edited by Salem; 11-08-2011 at 11:13 AM. Reason: remove stupid formatting tags from the code

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Based on the text description, I would write this...

    Code:
    int FindFixedPoint(int *array, int size)
      { int i;
    
         for (i = 0; i < size; i++)
            if (array[i] == i)
              return i;
    
         return -1;  // no fixed point
    }

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    > I have tried to write the following code...but got infinite loop error
    So what do you think the continue statement is doing for you?

    Have you tried running (and single stepping) the code in a debugger to see if high/low are actually converging on a mid-point in the array?
    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
    Registered User
    Join Date
    May 2009
    Posts
    2,774
    Hint: if this if is true; do you not wish to break out of the loop?
    Code:
          if(a[mid]==mid )
     
            {
     
              printf("Present = %d \n",a[mid]);                
     
            }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fixed point arithmatic imp in c
    By django in forum C Programming
    Replies: 7
    Last Post: 09-05-2011, 07:10 PM
  2. Fixed point opperations?
    By Devils Child in forum C++ Programming
    Replies: 5
    Last Post: 01-28-2008, 11:46 AM
  3. Fixed point MOD (for sin LUT)
    By Pea in forum C Programming
    Replies: 0
    Last Post: 04-10-2005, 07:03 PM
  4. fixed point / floating point
    By confuted in forum Game Programming
    Replies: 4
    Last Post: 08-13-2002, 02:25 PM
  5. Floating point faster than fixed-point
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 11-08-2001, 11:34 PM

Tags for this Thread


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