c++ Gobi: Mam listę posortowaną i przez wyszukiwanie połówwkowe chce policzyć ilość ruchów do znalezienia określonej liczby w tm zbiorze. Jak zaimplementowac ten problem w c++

g: ta liczba nie przekracza log₂N, gdzie N to długość listy. Jeśli chcesz wiedzieć dokładnie dla określonego miejsca listy, to trzeba po prostu wykonać to przeszukiwanie i policzyć kroki.

jc: Jeśli to prawdziwa lista, to nie ma znaczenia, czy jest posortowana, czy nie (chyba, że szukanego elementu nie ma na liście). średnia liczba pytań = (liczba elementów)/2 Jak sobie wyobrażasz wyszukiwanie połówkowe? Jak znajdziesz środek?

Gobi: założmy że mam [1 2 3 4 5] i chcę wyszukać 5 i chodzi o ilość ruchów

jc: Jak zaczniesz od lewej strony, to na 5 trafisz dopiero na końcu. Jak zaczniesz od prawej, to od razu masz 5.

Gobi: nie umiem tego napisć w c++

jc: Czy na pewno takie było polecenie? Czy zostało użyte słowo lista, czy tablica? Listę możemy przeglądać tylko element po elemencie od jednego końca do drugiego.

Gobi: lista uporzadkowana od najmniejszej do największej liczby

Gobi: nikt nie pomoze?

Gobi: http://www.iii-lo.tarnow.pl/informatyka/ladustrone.php?p1=informatyka&p2=40 chodzi o taki program jak tu tylko. Chodzi mi o zadnie 2: Aby podany algorytm zwracał informację liczbie wykonanych kroków.

jc: Dopisz coś takiego: while(Lewy<=Prawy){ kroki ++; .... return s + " Liczba krokow = " + (kroki).ToString();

Adamm: jc, mam pytanie, nie w temacie jeśli mam jakieś równanie x₁+x₂+x₃=9 (np.) i mam na x_i jakieś ograniczenia, załóżmy 0≤x₁≤3, 1≤x₂≤9, 5≤x₃≤8, to jak mogę znaleźć rozwiązania takiego równania w liczbach całkowitych za pomocą funkcji tworzących?

Gobi: A jak tu dopisć aby pokazywał te kroki: #include<iostream> using namespace std; int main() { int tablica[6] = { 7,9,13,23,89,666 }; int liczba, n = 6, l, p, s; cout << "Podaj jaki element znalezc: "; cin >> liczba; l = 0; p = n−1; while (true) { if (l > p) { cout << "Nie odnaleziono szukanego elementu" << endl; break; } s = (l+p)/2; if (tablica[s] == liczba) { cout << "Odnaleziono liczbe " << liczba << " pod indeksem " << s+1 << endl; break; } else if (tablica[s] < liczba) l = s+1; else p = s−1; } return 0; }

Gobi: jak to zrobic?

Gobi: ok juz wiem

Gobi: nie jednak nie wiem

Gobi: Nikt nie wie

PDG: https://forum.pcformat.pl/Programowanie-f http://cpp0x.pl/forum/ Spróbuj jak nie tutaj, to na tamtych forach. Tam jest więcej informatyków co mogą pomóc.

jc: int main() { int tablica[6] = { 7,9,13,23,89,666 }; int liczba, n = 6, l, p, s, k; cout << "Podaj jaki element znalezc: "; cin >> liczba; l = 0; p = n−1; k = 0; while (true) { k++; if (l > p) { cout << "Nie odnaleziono szukanego elementu" << endl; break; } s = (l+p)/2; if (tablica[s] == liczba) { cout << "Odnaleziono liczbe " << liczba << " pod indeksem " << s+1 << endl; break; } else if (tablica[s] < liczba) l = s+1; else p = s−1; } cout << "Liczba krokow = " << k << endl; return 0; }

Gobi: Niestety za duzo o 1 liczy liczbe kroków jak nie ma go w tablicy

jc: Przenieś k++ tam, gdzie uważasz. Skąd mam wiedzieć, czym dla Ciebie jest krok?

Gobi: np gdy mamy [1 2 4] i szukamy 3 1 krok środkowa liczba to dwa więc 2<3 wiec zostało do zbadania [1] 2 krok 3>1 wiec nie ma tam liczby 3 czyli krok=2

Gobi: ok ju wiem chyba