Wyszukiwanie i zwracanie wartości

0

Witam wszystkich użytkowników.

Proszę o pomoc w następującym problemie:

Chcę napisać funkcję w C++ która danym zakresie liczb całkowitych np:

Przykład 1 ( 1, 2, 3, 4, 6, 7, 9, 10)
Przykład 2 ( 3, 4, 5, 6, 7, 8, 9, 10)

sprawdzi czy jest ciągłość bądź czy liczby następują kolejno po sobie jeśli nie to niech zwróci pierwszą wolną wartość. W przykładzie 1 była by to liczba 5, w przykładzie 2 była by to liczba 1.

Pozdrawiam i z góry dziękuję za pomoc.

0
int funkcja(int *tab,int ile)
{
    int *pomoc=new int[ile];
    for(int i=0;i<ile;i++)
        pomoc[i]=(i+1);

    for(int i=0;i<ile;i++)
        if(tab[i]!=pomoc[i])
            return pomoc[i];

    return 0;
} 

nie wiem czy dokladnie o takie coś chodziło :)

0
cysiej napisał(a)
int funkcja(int *tab,int ile)
{
int *pomoc=new int[ile];

a gdzie zwalniasz te tablice?

poza tym, na ten problem, raczej tablica pomocnicza nie jest potrzebna.. zwlaszcza ze trzymasz w niej tylko ilosc obiegow petli, wiec rownie dobrze moglbys uzywac caly czas zmiennej "i", zoffsetowanej, i zapomniec o tablicy..

a tak w ogole, to:

int szukaj_dziury(int *wartosci, int iloscwartosci)
{
    int idx = 1;
    while(idx < iloscwartosci)
    {
        int poprzedni = wartosci[idx-1];
        int aktualny = wartosci[idx];
        if(poprzedni - aktualny > 1)
            ....
        else
            ....
    }
    ....
}

w miejsce kropek trzeba cos powstawiac, ale chyba widac sens..

0

Jeżeli tablica nie ma powtórek to można to zrobić w czasie O(log(N)) zamiast O(N):

#include <iostream>
using namespace std;

unsigned findhole(unsigned tb[],unsigned count)
  {
   unsigned min=0,max=count;
   while(min<max)
     {
      unsigned mid=(max+min)>>1;
      if(tb[mid]>mid+1) max=mid; else min=mid+1;
     }
   return min+1;
  }

int main()
  {
   unsigned tb1[]={1, 2, 3, 4, 6, 7, 9, 10},stb1=sizeof(tb1)/sizeof(*tb1);   
   unsigned tb2[]={3, 4, 5, 6, 7, 8, 9, 10},stb2=sizeof(tb2)/sizeof(*tb2);
   cout<<findhole(tb1,stb1)<<endl;
   cout<<findhole(tb2,stb2)<<endl;
   cin.sync(); cin.get();
   return 0;
  }

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0