Cześć
Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub podobny ciąg
liczb:
1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
1-4,6-8,14-16,190-192,300

??

do góry

On 2013-10-28, d...@g...com <d...@g...com> wrote:
> Cześć
> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub podobny
ciąg liczb:
> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
> 1-4,6-8,14-16,190-192,300

Zdefiniuj "sprawny". Oczekujesz lepszego niż O(n) od długości ciągu
wejściowego?

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu 28.10.2013 o 16:51 <d...@g...com> pisze:

> Cześć
> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub
> podobny ciąg liczb:
> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
> 1-4,6-8,14-16,190-192,300
>
> ??

w kółko
wczytaj liczbę
jeśli jest o 1 większa od poprzedniej
poszerz ostatni zakres
w przeciwnym wypadku
utwórz nowy zakres

do góry

W dniu 2013-10-28 17:01, Piotr pisze:
> W dniu 28.10.2013 o 16:51 <d...@g...com> pisze:
>
>> Cześć
>> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki
>> lub podobny ciąg liczb:
>> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
>> 1-4,6-8,14-16,190-192,300
>>
>> ??
>
> w kółko
> wczytaj liczbę
> jeśli jest o 1 większa od poprzedniej
> poszerz ostatni zakres
> w przeciwnym wypadku
> utwórz nowy zakres


Zakładając, że ciąg jest posortowany.

Jeśli nie jest, mamy O(n log(n))

Ale nie bójmy się, akademicka (akademikowa) teoretyczność*)
idzie z pomocą.

Weźmy strukturę/algorytm find-union.
Zbiory (te z f-u) wzbogaćmy informacją o najmniejszym i największym
elemencie (aktualizowana O(1)). Trzeba to

Teraz już prosto. Na początek koszyczek zbiorów pusty.

while wejście niepuste
odczytaj nową liczbę -> x
if (!(find(x)))
nowy_zbiór(x)
if (find(x-1)) union(x,x-1)
if (find(x+1)) union(x,x+1)

Na koniec, przechodząc wszystkie zbiory dostajemy, również
nieposortowany, zestaw przedziałów.

Złożoność O ( dziwna_funkcja(n) * n )

zaś dziwna funkcja (Ackermana) rośnie bardzo powoli,
wolniej niż logarytm iterowany (ile razy trzeba zlogarytmować
liczbę, by dostać <1).

*) obstawiam, że sortowanie i tak może wygrać dla ludzkich
zbiorów danych.



:)

pzdr
bartekltg

do góry

On Mon, 28 Oct 2013 23:22:55 +0100, bartekltg <b...@g...com>
wrote:

>
>Złożoność O ( dziwna_funkcja(n) * n )
>
>zaś dziwna funkcja (Ackermana) rośnie bardzo powoli,
>wolniej niż logarytm iterowany (ile razy trzeba zlogarytmować
>liczbę, by dostać <1).

O ile mnie pamiec nie myli, funkcja Ackermana ma 2 argumenty. I
bynajmniej nie rosnie powoli

A.L.

do góry

W dniu 2013-10-28 23:38, A.L. pisze:
> On Mon, 28 Oct 2013 23:22:55 +0100, bartekltg <b...@g...com>
> wrote:
>
>>
>> Złożoność O ( dziwna_funkcja(n) * n )
>>
>> zaś dziwna funkcja (Ackermana) rośnie bardzo powoli,
>> wolniej niż logarytm iterowany (ile razy trzeba zlogarytmować
>> liczbę, by dostać <1).
>
> O ile mnie pamiec nie myli, funkcja Ackermana ma 2 argumenty. I
> bynajmniej nie rosnie powoli


Jasne, miałem na myśli "odwrotną" funkcja Ackermana. Pośpiech
.
http://en.wikipedia.org/wiki/Ackermann_function#Inve
rse

Też ma dwa argumenty. Tzn może mieć, zależnie, jak tę
odwrotność zdefiniujemy. Można prosto, odwrotność funkcji
f(x) = A(x,x), ( odwrotność A(4,n) to logarytm iterowany :)
a można i sprytniej, ale ta defincja chyba jest nawet
zrobiona pod algorytm.


Za poważnie się na ten wątek zrobiło;-)

pzdr
bartekltg

do góry

d...@g...com wrote:

> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub podobny
ciąg liczb:
> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
> 1-4,6-8,14-16,190-192,300

Zobacz kod jakiegoś uniksowego czytnika newsów (pine, alpine, tin, slrn).
Plik .newsrc, z którego korzystają, właśnie tak wygląda.

--
"zanim nastala era internetu, kazdy wiejski glupek siedzial w swojej wiosce"
http://www.chmurka.net/

do góry

W dniu poniedziałek, 28 października 2013 16:51:13 UTC+1 użytkownik ToMi napisał:
> Cześć
>
> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub podobny
ciąg liczb:
>
> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
>
> 1-4,6-8,14-16,190-192,300
>

okrotnie latwe zadanie dobre nawet mysle do uczenia programowania w szkole czy gdzies

aczkolwiek jak probuje to zakodowac nasuwaja sie
pewne uwagi

1) da sie to zapisac ale przyklad nieco obnaza
niedostatki wspolczesnych jezykow programowania
bo z czegos tak prostego robi sie mala lamigłowka

2) o ile juz zapisac to latwiej majac dostep do dancyh we wy w postaci tablic a nie w
postaci
api strumienia (te cholerne strumienie sa wlasnie
trudniejsze w zakodowaniu i mniej poreczne)

w jakims dobrze ustruktaryzowanym jezyku powinno
sie to dac podzielic na jakies wydzielone etapy
konkretnie na przyklad trzy

(1) petla ma sie wywolac dla wszystkich sekwencyjnych par przyleglych liczb (po calym
inpucie)
(2) porownuje sie te pary jesli druga wartosc jest o jeden mniejszy niz pierwszy
wywolaj pisanie minusa (3) ale takiego ze jesli ostatnio w outpucie jest minus to nie
wypisuj nic)
natomiast jesli nie wypisz liczbe

(co gorsza to cholerstwo w ujeciu wyzej mimo ze problem jasny jest w zakodowoaniu
niesymetryczne

w ujeciu w c to byloby to cos podobnego do - aczkolwiek to tutaj to jest co nieco
pseudokod

print(input[0];

for(int i=1; i<length of(input); i++)
{
int last_printed_is_minus = 0;

if(input[i]==input[i-1])
if(last_printed_is_minus)
last_printed_is_minus =1,
print("-");
else
last_printed_is_minus =0,
print(i);

}

do góry

On Monday, October 28, 2013 4:51:13 PM UTC+1, ToMi wrote:
> Cześć
>
> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub podobny
ciąg liczb:
>
> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
>
> 1-4,6-8,14-16,190-192,300

A ile masz tych liczb?
Jaki jest ich zakres?

w.

do góry

W dniu 28.10.2013 16:51, d...@g...com pisze:
> Cześć
> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki lub podobny
ciąg liczb:
> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
> 1-4,6-8,14-16,190-192,300
>
> ??
>

Można by to bardziej zoptymalizować np. poprzez wywoływanie
string.format dopiero gdy jest potrzebne a nie w każdym kroku
iterowanego ciągu, ale ogólnie masz tu algorytm który robi to w jednym
przebiegu:

Do zweryfikowania na: http://repl.it/languages/Lua

local a={1,2,3,4,6,7,8,14,15,16,190,191,192,300}
local ret={}

local startval,lastval

for i=1,#a do
if startval and lastval and lastval==a[i]-1 then
ret[#ret]=string.format("%d-%d", startval, a[i])
else
table.insert(ret, a[i])
startval=a[i]
end
lastval=a[i]
end

-- pokazywanie wyniku

print(table.concat(ret,","))

do góry