wyszukiwanie przez interpolacje

Witam,

coś mi nie zawsze dobrze działa wyszukiwanie przez interpolację, niby liczba w tablicy jest, a program kończy działanie.

 #define MAX 25
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stdlib.h>

using namespace std;

int main()
{
int tab[MAX];
int i=0, j=0, liczba=0, x=0, u=0, temp=0, h=0, w=0, e=0, p=0, k=0,z=0;
float licznik_porownan=0, licznik_zamiany=0;
int wybor, l, t;
float srednia_operacji=0;

srand((unsigned)time(NULL));

// POCZATEK WYPELNIANIA TABLICY LICZBAMI LOSOWYMI
for (i=0; i<MAX; i++)
{
 tab[i]=rand() % (MAX) + 0;
}
// KONIEC WYPE£NIANIA TABLICY


// POCZATEK SORTOWANIA TABLICY - INSERTION SORT
  for(j=0;j<MAX-1;j++)
  {
    for(i=0;i<MAX-1;i++)
    {
        if(tab[i]>tab[i+1])
        swap(tab[i],tab[i+1]);
    }
  }
// KONIEC SORTOWANIA TABLICY - INSERTION SORT


// POCZATEK WYSWIETLANIA TABLICY

        for (i=0; i<MAX; i++)
        {
            cout << tab[i] << "\t";
            if((i+1)%5==0)
            cout << endl;
        }

// KONIEC WYSWIETLANIA TABLICY //

// POCZATEK WYSZUKIWANIA INTERPOLACYJNEGO
cout << "Jakiej liczby szukasz?" << endl;
cin >> x;

i=0;
j=MAX-1;

    if (x < tab[0])
    {
        cout << "Brak szukanego elementu" << endl;
        system("pause");
        return(-1);
    }

    if (x > tab[MAX-1])
    {
        cout << "Brak szukanego elementu" << endl;
        system("pause");
        return(-1);
    }

    if (x == tab[0])
    {
        cout << "Element jest na pierwszej pozycji" << endl;
        system("pause");
        return 0;
    }

    if (x==tab[MAX-1])
    {
        cout << "Element jest na ostatniej pozycji" << endl;
        system("pause");
        return(MAX-1);
    }

    p=0;

    while (i < j-1)
    {
          k=(i+(j-i)*(x-tab[i])/(tab[j]-tab[i]));

          if(x==tab[k])
          {
               cout << "Szukany element wynosi " << k << endl;
               system("pause");
               return(k);
          }
            // if((i = k) || (j = k)) - sprawdzic co robi

          if (x<tab[k]) j=k;
          else i=k;

            p++;

          if (p==MAX)
          return(-1);
    }
// KONIEC WYSZUKIWANIA INTERPOLACYJNEGO
cout << endl;
srednia_operacji=(licznik_porownan+licznik_zamiany)/2;
cout << endl;
// POCZATEK WYSWIETLANIA LICZNIKOW //
cout << "Licznik porownan wynosi -> " << licznik_porownan << endl;
cout << "Licznik zamian wynosi -> " << licznik_zamiany << endl;
// cout << "Srednia operacji wynosi -> " << srednia_operacji << endl;
// KONIEC WYSWIETLANIA LICZNIKOW //
system("pause");
return 0;
}

Debugger?

a ja radzę przepisać tak by każda funkcja (zwłaszcza main) mieściła się w maksymalnie 15 linijkach (preferowana ilość 5).
Zamiast otaczać kod głupimi komentarzami zamknij te fragmenty w funkcjach o rozsądnych nazwach np:

void wyswietlTablice(int tab[], int n) {
   ...
}

void sortuj(int tab[], int n) {
 ...
}

void wypelnijLosowo(int tab[], int n)

Spróbowałem to pochować w funkcjach i wygląda to tak.

#define MAX 100
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stdlib.h>

using namespace std;

int tab[MAX], x;

void wypelnijLosowo()
{
    srand((unsigned)time(NULL));
    for (int i=0; i<MAX; i++)
    {
     tab[i]=rand() % (MAX) + 0;
    }
}

void sortuj()
{
  for(int j=0;j<MAX-1;j++)
  {
    for(int i=0;i<MAX-1;i++)
    {
        if(tab[i]>tab[i+1])
        swap(tab[i],tab[i+1]);
    }
  }
}

void wyswietlTablice()
{
        for (int i=0; i<MAX; i++)
        {
            cout << tab[i] << "\t";
            if((i+1)%5==0)
            cout << endl;
        }
}

int wyszukiwanieInterpolacyjne()
{
cout << "Jakiej liczby szukasz?" << endl;
cin >> x;

int i=0;
int j=MAX-1;

    if (x < tab[0])
    {
        cout << "Brak szukanego elementu" << endl;
        system("pause");
        return(-1);
    }

    if (x > tab[MAX-1])
    {
        cout << "Brak szukanego elementu" << endl;
        system("pause");
        return(-1);
    }

    if (x == tab[0])
    {
        cout << "Element jest na pierwszej pozycji" << endl;
        system("pause");
        return 0;
    }

    if (x==tab[MAX-1])
    {
        cout << "Element jest na ostatniej pozycji" << endl;
        system("pause");
        return(MAX-1);
    }

    int p=0;

    while (i < j-1)
    {
          int k=(i+(j-i)*(x-tab[i])/(tab[j]-tab[i]));

          if(x==tab[k])
          {
               cout << "Szukany element wynosi " << k << endl;
               system("pause");
               return(k);
          }
            // if((i = k) || (j = k)) - sprawdzic co robi

          if (x<tab[k]) j=k;
          else i=k;

            p++;

          if (p==MAX)
          return(-1);
    }
}
int main()
{
wypelnijLosowo();
sortuj();
wyswietlTablice();
wyszukiwanieInterpolacyjne();
system("pause");
return 0;
}
 

Ten fragment:

            p++;
 
          if (p==MAX)
          return(-1);

to jakieś bzdurne nieporozumienie.

Zapomniałeś że masz duże prawdopodobieństwo że: tab[j]-tab[i] wyniesie zero (cholero nie dziel przez zero).

Wiem, wiem, ale muszę to zrobić według pseudokodu (w załączniku).

I wszystko byłoby fajnie, tylko że niektóre liczby całkowicie pomija i jakby ich wykrywał. Przykład również w załączniku.
28 występuje dwa razy, a mimo tego nie wypisuje kompletnie nic.

Może weź i poczytaj czym jest pseudokod, jak już przeczytasz to wróć do czytania mojego poprzedniego postu.