porządek szarkowskiego - który pojemnik

mam napisać porządek szarkowskiego używając dowolnego pojemnika;
pytanie moje: którego użyć aby był najbardziej optymalny i dlaczego.
dzięki.

co znaczy napisac porzadek?
konkret wejscie-wyjscie, co chcesz trzymac?
moze uzyj kartki :P

"Porządek Szarkowskiego" tak to się nazywa.
tak jak masz "Ciąg Fibonacciego" tak masz "porządek szarkowskiego".
mam to zrobić na pojemnikach i nie wiem który zrobić.

hmmm wyobraz sobie ze nie jestem az takim ignorantem i sprawdzilem co to za porzadek ;]
i o ile dobrze pamietam z teorii mnogosci porzadek to pewna relacja (nie bede rozpisywal sie jaka, kazdy chyba umie uzyc wikipedii)
wiec

1. masz pewna relacje
2. pewnie powinienes miec jakies dane wejsciowe (liczby N, bo widzialem ze jest to porzadek w zbiorze N)
3. zastosowac relacje porzadku do ? posortowania lub spawdzenia danych wejsciowych i wyplucie jakiegos wyjscia
   czy cos zle rozumuje?
   przyznam ze cos mi nie pasuje w rysuneczku na wiki http://pl.wikipedia.org/wiki/Twierdzenie_Szarkowskiego, czemu w ostatnim wierszu jest 2^{3 < 2}2 < 2^1 < 1, jakos nie klei sie to z powyzszymi wierszami, jak masz lepsze wytlumaczenie tego twierdzenia to daj link

@massther, wszystko jest w porządku. W uporządkowaniu Szarkowskiego liczb naturalnych potęgi dwójki sa na końcu uporządkowane malejąco.
@Neo, co znaczy "napisać porządek Szarkowskiego"? Być może chodzi o to by dla danych dwóch liczb naturalnych rozstrzygnąć, która jest wcześniej w porządku Szarkowskiego. Wtedy zapewne żaden pojemnik nie jest potrzebny.

Eee a nie chodzi czasem o zbudowanie takiej macierzy: http://upload.wikimedia.org/math/7/e/8/7e8592f2bad36d4624119f34da9a1133.png
lub zwrócenie n-tego elementu ciągu utworzonego z tej macierzy?

treść zadania

Jak rozumiem, masz mierzyć i porównywać tylko czas odpowiedzi na pytanie:

na którym miejscu jest liczba i
. Natomiast czas tworzenia pojemnika jest nieważny. Jestem pewien, że najkrótszy czas odpowiedzi da hashmapa zawierająca pary (i,pozycja liczby i w ciągu).

możesz coś więcej napisać na ten temat? lub jakieś linki

Po siszarpowemu hashmapa to chyba Dictionary: http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

czyli najlepiej użyć hashmapy - w c# będzie to słownik;
pytanie: jak uzasadnić ten wybór?
ma ktoś z Was algorytm na generowanie tych liczb? bo niestety mnie się nie udało znaleźć...

Ja też nie znalazłem (może dlatego że nie szukałem).
Żebyś nie miał za łatwo dostajesz program w pythonie

# _*_ coding: utf-8 _*_
from datetime import *

n=int(raw_input("Podaj liczbę n: "))

start=datetime.today()
liczby=[]
wykladnik=0
while 3*(2**wykladnik)<=n:
   k=1
   m=2**wykladnik
   while ((2*k+1))*m<=n:
      liczby.append(((2*k+1))*m)
      k+=1
   wykladnik+=1
wykladnik=0
while 2**wykladnik<=n:
   wykladnik+=1
wykladnik-=1
while wykladnik>=0:
   liczby.append(2**wykladnik)
   wykladnik-=1
slownik={}
for i in range(n):
   slownik[liczby[i]]=i+1
stop=datetime.today()
print "Czas tworzenia pojemnika: "+str(stop-start)
start=datetime.today()
for k in range(1,n+1):
   m=slownik[k]
stop=datetime.today()
print "Czas szukania: "+str(stop-start)

Podaj liczbę n: 1000000
Czas tworzenia pojemnika: 001:360000
Czas szukania: 000.281000
Ostatni czas, to suma szukania wszystkich liczb od 1 do 1mln.

mozesz tez przetestowac Hashtable - chociaz tu pewnie narzut na boxing/unboxing bedzie spory
lub SortedList<K,T>, SortedDictionary<K,T>
lub zwykla List<T> i uzywac BinarySearch z wlasnym comparerem
chociaz na pierwszy rzut oka wydaje sie ze zwykly Dictionary bedzie ok, to w praktyce moze byc roznie
wszystko zalezy od ilosci danych, przy pewnych strukturach bedzie narzut przy wstawianiu nowych danych, w innych moze szybciej dzialac wyszukiwanie

moze okazac sie ze warto uzyc jakis drzew AVL, B-Tree - nie ma standardowych implementacji w .net ale latwo znalezc niezle implementacje w sieci

@ne0, ja rozumiem zadanie tak, że wybór kontenera masz uzasadnić doświadczalnie.
Napisałem program w Javie do zabaw z porządkiem Szarkowskiego. Kontenerem jest HashMap(Integer,Integer>. Czasy są trochę lepsze niż dla Pythona: dla przedziału [1;1mln] czas tworzenia kontenera poniżej 0,5 sekundy, czas szukania około 80 milisekund.
Gdybyś był zainteresowany samym algorytmem tworzenia kontenera napisanym w Javie, to mogę go wrzucić na forum (około 600 bajtów).

Algorytm można opisać tak;

1. tworzę n-elementową tablicę tab
2. tworzę zmienną m=1
3. zapisuję do tablicy (od początku) liczby nieparzyste m3,m5,m*7, <=n
4. zwiększam m dwukrotnie
5. jeżeli m*3<=n wracam do punktu 3
6. od końca tablicy wpisuję potęgi dwójki 1,2,4, >=n
7. tworzę pustą Hashmapę map
8. czytam kolejne (od początku) elementy tablicy tab, do map dodaję parę (tab[i],i+1)

jakbyś mógł to proszę wrzuć :)