Witamy na forum PC Format Zapraszamy do REJESTRACJI


Użytkownicy przeglądający ten wątek: 1 gości

Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy

#1
Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Witam,
Mam za zadanie obliczyć ile razy zostaną wykonane instrukcje przypisania w algorytmie wyszukiwania największej liczby w tablicy.

Tablica zawiera elementy Tab [1.....n]
pseudokod
Kod:
1.max=Tab[1]
for i=2 to n
do if A[i]>max
2.then max=A[i]
return m
Mam to wskazać ile razy wykona się przypisanie 1. oraz 2. dla przypadków optymistycznego, pesymistycznego oraz średniego.

Dla optymistycznego wywnioskowałem wartość 1 i 0. Mamy przypadek gdzie na 1 miejscu znajduje się max(my jeszcze o tym nie wiemy) więc przypisujemy go do max bo tak działa algorytm. Przechodzimy całą tablicę i okazuje się, że żadna z wartości nie była większa dlatego nie weszliśmy do ifa i nie wykonało się przypisanie 2.

Dla pesymistycznego wywnioskowałem wartość 1 oraz n. Pierwsze przypisanie musi być wykonane to wynika z algorytmu. Natomiast n, ponieważ przechodzimy przez n elementów tablicy i okazuje się, że nasz największy element to ostatni element tablicy, więc przypisanie wykona się n razy?(tego nie jestem pewien bo przecież wartości w tablicy mogą być różne i inny wynik przypisań 2 będzie dla tablicy 1 7 5 8 a inny dla 3 1 7 5 8).

Dla średniej znowu pierwsze przypisanie będzie miało wartość 1,ponieważ wykona się raz na początku natomiast nie jestem pewien tego drugiego przypisania myślę nad n/2 ale tu mi coś podpowiada ,że to w ogóle błędny tok rozumowania.

Chciałbym się dowiedzieć czy zmierzam w dobrym kierunku z tymi swoimi przemyśleniami.

Edit:Teraz już jestem pewien, że te n/2 to błędne myślenie. Znalazłem uzasadnienie, że w n elementowej tablicy prawdopodobieństwo, że dany element jest większy od poprzednich prowadzi do szeregu harmonicznego czyli średni czas wyszukiwania będzie 1/n ?
Pozdrawiam,
Pamietaj nie musisz mi pomagac ale i tobie moze byc potrzebna pomocOczy
 System operacyjny: windows_seven Przeglądarka: chrome
#2
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Przypisanie max=Tab[1] będzie zawsze tylko jedno.

Przypadek pesymistyczny - 2 przypisanie: n-1 (sam napisałeś, że pętla ma się wykonać od 2 do n Oczko ).

Przypadek pośredni: nie bardzo rozumiem o co ci chodzi (mieszasz iteracje z czasem).

Dochodzi jeszcze kwestia czy wartości w tablicy mogą się powtarzać.
Nie pomagam na PW (ew. odpłatnie). 
I osobom z roszczeniowym podejściem. I osobom niedbającym o poprawność językową.
Jak podawać logi
Jeśli nie odpowiadam w danym wątku przez >3 dni - proszę o przypomnienie na PW z linkiem do wątku w treści.




 System operacyjny: windows_xp_2003 Przeglądarka: firefox
#3
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Tak z tą 2 nie zauważyłem mój błąd.
Nic nie zostało wspomniane o tym aby wartości mogły się powtarzać więc zakładam, że nie trzeba będzie rozpatrzyć takiego przypadku.
Co do złożoności to inne zadania mają ją obliczyć ja mam tylko wskazać ile razy zostaną przypisania przeprowadzone dla 3 przypadków.
Jeżeli chodzi o średnią to dokładnie chodzi o przykład taki : "Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych.". Optymistyczna dla najkorzystniejszego zestawu danych a pesymistyczna dla najgorszego.
Pamietaj nie musisz mi pomagac ale i tobie moze byc potrzebna pomocOczy
 System operacyjny: windows_seven Przeglądarka: chrome
#4
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Skłaniałbym się ku wynikowi (n-1)/2.
Nie pomagam na PW (ew. odpłatnie). 
I osobom z roszczeniowym podejściem. I osobom niedbającym o poprawność językową.
Jak podawać logi
Jeśli nie odpowiadam w danym wątku przez >3 dni - proszę o przypomnienie na PW z linkiem do wątku w treści.




 System operacyjny: windows_xp_2003 Przeglądarka: firefox
#5
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Sprawa wydaje się być bardziej skomplikowana.
Kod:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int maks(const vector<int>& t)
{
    int m = t[0], x = 0;
    if (m == t.size())
        return 0;
    for (int i = 0; i < t.size(); i++)
        if (t[i] > m)
        {
            m = t[i];
            x++;
            if (m == t.size())
                break;
        }
    return x;
}

void print_array(const vector<int>& t)
{
    for (int i = 0; i < t.size(); i++)
        cout << t[i] << ' ';
}

int main()
{
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, N;
    vector<int> vec;
    long long n, x;
    const int r = sizeof(data) / sizeof(data[0]);
    for (int i = 2; i <= r; i++)
    {
        vec = vector<int>(data, data + i);
        N = maks(vec);
/*        print_array(vec);
        cout << ": n = " << N << endl;
*/        n = N;
        x = 1;
        while (next_permutation(vec.begin(), vec.end()))
        {
            N = maks(vec);
/*            print_array(vec);
            cout << ": n = " << N << endl;
*/            n += N;
            x++;
        }
        cout << i << " elementów: " << n << '/' << x << '=' << n / (double)x << endl;
    }
    return 0;
}
Przy większej próbie widać, że punkty układają się w prostą.
 System operacyjny: linux Przeglądarka: firefox
#6
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Sprawdziłem empirycznie: dla 100 prób, każda dla 101 elementów (100 porównań "czy max") - wyniki są od 0 do c.a. 7. Nie wiem jak się układają - ale na pewno nie w linię prostą (rozkład normalny to też nie jest - sztywne ograniczenie z lewej > ale już bardziej. Może Chi-kwadrat?).

https://www.sendspace.com/file/qe0fpi
Nie pomagam na PW (ew. odpłatnie). 
I osobom z roszczeniowym podejściem. I osobom niedbającym o poprawność językową.
Jak podawać logi
Jeśli nie odpowiadam w danym wątku przez >3 dni - proszę o przypomnienie na PW z linkiem do wątku w treści.




 System operacyjny: windows_xp_2003 Przeglądarka: firefox
#7
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Doszedłem do wniosku, że przesadziłem nieco z tym - na początku też chciałem zaproponować ten wzór (1 + n-1)/2, ale nie wiem, co mnie natchnęło, aby przejrzeć wszystkie kombinacje. Oczywiście Twoje podejście jest rozsądniejsze.
 System operacyjny: linux Przeglądarka: firefox
#8
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Wyniki są na pewno bliższe prawdy (mimo pseudo-losowości i tego, że wartości mogą się powtarzać). W kodzie był błąd - poprawiłem > teraz wyniki są w granicach 10 z maksymalnymi wartościami 3-4.
https://www.sendspace.com/file/uwmk6v

Co nie zmienia faktu, że nie mam pomysłu jak to teoretycznie wyliczyć. Jest to z pewnością prawdopodobieństwo warunkowe, ale dla n>2 obliczenia mnie przerastają... Oczko .
Nie pomagam na PW (ew. odpłatnie). 
I osobom z roszczeniowym podejściem. I osobom niedbającym o poprawność językową.
Jak podawać logi
Jeśli nie odpowiadam w danym wątku przez >3 dni - proszę o przypomnienie na PW z linkiem do wątku w treści.




 System operacyjny: windows_xp_2003 Przeglądarka: firefox
#9
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
Te (n-1)/2 wygląda całkiem sensownie dla mnie. Jest n-1 porównań maksymalnie to ile może być średnio? (n-1)/2. Mam jeszcze jedno pytanie dlaczego np. średnia by nie mogła wynosić (n-1)/(n/2)? albo (n-1)/n
Pamietaj nie musisz mi pomagac ale i tobie moze byc potrzebna pomocOczy
 System operacyjny: windows_seven Przeglądarka: chrome
#10
RE: Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy
n/2 to też była moja 1-sza myśl - ale jest błędna. Byłoby to słuszne, gdyby chodziło o c.a. taki algorytm (suma elementów większych od średniej):
Kod PHP:
1.sr=średnia(Tablica)
for 
i=1 to n
do if Tab[i]>sr
2.m
=m+Tab[i]
return 

Ponieważ śerdnia jest stała >> prawdopodobieństwo że kolejny el. będzie > średniej też jest stałe (1/2).

Natomiast w twoim przypadku każde przypisanie zmniejsza prawdopodobieństwo kolejnego (zawęża się przedział w którym ma się znajdować liczba).

Przykład:
Tab=[2, 5, 6, 1, 3, 4] >> przedział <1,6>
1. max=Tab[1]=2. P(kolejna większa)=4/6 > bo tylko 4 elementy na 6 są większe.
2. Tab[2]>max >> podstawienie 1: max=Tab[2]=5. P(kolejna większa)=1/5 > bo tylko 1 element na 5 jest większy.
3. Tab[3]>max >> podstawienie 2: max=Tab[3]=6. P(kolejna większa)=0/4 > bo większych nie ma (nieważne na ile).
Nie pomagam na PW (ew. odpłatnie). 
I osobom z roszczeniowym podejściem. I osobom niedbającym o poprawność językową.
Jak podawać logi
Jeśli nie odpowiadam w danym wątku przez >3 dni - proszę o przypomnienie na PW z linkiem do wątku w treści.




 System operacyjny: windows_xp_2003 Przeglądarka: firefox
Programy: Polecane / Nowe / Inne




Podobne wątki (Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  Java- wypisanie liczb, które nie są podane w tablicy , wypisanie liczb z tablicy all? ccomp 10 13431 16.07.2017, 20:10
Ostatni post: ccomp
  Wyszukiwanie w tablicy soul1648 3 6529 01.04.2017, 14:26
Ostatni post: Ajgor
  [C++] Działanie na tablicy znakowej saba13579 8 6102 21.03.2017, 22:30
Ostatni post: Szachista

Skocz do:


Wybrane wątki (Wyznaczyć ilość przypisań dla algorytmu wyznaczającego maksymalną wartość w tablicy)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  Algorytm Genetyczny C pr1991 3 8273 26.10.2017 11:52
Ostatni post: Szachista
  Program C++ do pola i objętości mistrz18 2 8317 18.10.2017 23:10
Ostatni post: Ajgor
  [C]Część wspólna 2 przedziałów. polak3018 2 7539 13.10.2017 16:43
Ostatni post: ptrick
Question Wyznaczanie maksimum spośród 5 liczb - schemat blokowy mistrz18 5 7922 05.10.2017 19:49
Ostatni post: broda99
  Batch - odczytywanie temperatury karty graficznej i zapisywanie jej do zmiennej ~Anonim 4 7945 03.09.2017 21:41
Ostatni post: ~Anonim
  Kodowanie znaków w .bat kkkkk2105 4 9385 25.08.2017 14:38
Ostatni post: kkkkk2105
  Konwertowanie słów na liczby Java Blendow 5 7734 19.08.2017 21:17
Ostatni post: Szachista
  Kończenie i zamykanie skryptu vbs ottps 1 7188 16.08.2017 23:55
Ostatni post: broda99
  Podwojne menu wyboru w batch files kulis88 3 7529 12.08.2017 23:41
Ostatni post: broda99
  Walidacja tekstu w CSV,XLS w PHP Profedbond 9 8074 11.08.2017 09:10
Ostatni post: insanebear
  [VBS] String TheJohan8 5 7705 08.08.2017 00:11
Ostatni post: Ajgor
  Jaki kod pod buttony i progressbar w visualbasicu2010 Express? aktywny27 2 7029 06.08.2017 14:41
Ostatni post: ~Anonim
  [VB.Net] webbrowser a kody kreskowe DonCorleone 0 6595 03.08.2017 20:13
Ostatni post: DonCorleone
Ściana batch file ustawianie jednej wartosci zmiennej do kilku plikow kulis88 6 1995 03.08.2017 19:12
Ostatni post: kulis88
  [VBS] loop & if TheJohan8 0 6508 01.08.2017 18:40
Ostatni post: TheJohan8