-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Algorytmiczny problem lamera... :-)
Date: Mon, 06 Oct 2014 22:20:05 +0200
Organization: ATMAN - ATM S.A.
Lines: 147
Message-ID: <m0uthm$oe4$1@node1.news.atman.pl>
References: <1...@g...com>
<m0s8le$lfc$1@node2.news.atman.pl>
<2...@g...com>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1412626806 25028 89.73.81.145 (6 Oct 2014 20:20:06 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Mon, 6 Oct 2014 20:20:06 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101
Thunderbird/31.1.2
In-Reply-To: <2...@g...com>
Xref: news-archive.icm.edu.pl pl.comp.programming:206692
[ ukryj nagłówki ]On 06.10.2014 21:04, m...@g...com wrote:
> W dniu niedziela, 5 października 2014 22:11:26 UTC+2 użytkownik bartekltg napisał:
>
>> int i=0;
>>
>> while ( i<nElem )
>> {
>> MyOutFile << Tab[i] << ...;
>> int j=i+1;
>> while( (j<nElem) && (strcmp(Tab[j],Tab[i])==0) ) j++;
>> i=j;
>> }
>
>
> O, proszę! Ładne! :-)
>
> Skojarzyłem, że kiedyś musiałem różnie reagować w zależności od
> liczby
>wyrazów we wczytanym wierszu i męczył mnie podobny problem, więc tylko
>na nim się skupiłem...
> Zakładając, że elementy NIE sa posortowane, przychodzi mi tylko coś
>takiego do głowy:
>
> for (i = 0; i < nElem; i++)
> {
> for (k = 0; k < i; k++)
> if (strcmp(Tab[i], Tab[k]) == 0)
> goto NEXT;
>
> for (k = i + 1; k < nElem; k++)
> if (strcmp(Tab[i], Tab[k]) == 0)
> goto NEXT;
>
> MyOutFile << Tab[i] << ...
>
> NEXT:
> }
To jest kwadratowe.
Sortowanie jest n log(n) + algorytm powyżej (czy z std:z unique),
który jest linowy.
Nie ma porównania;-) Posortuj i rób jak poprzednio.
Jeśli chcesz je wypisywać w kolejności, w jakiej nadeszły,
możesz zapisać numer na pierwotnej liście, posortować
puścić unique, posortować po numerach nadejścia.
4 linijki, nadużywając języka.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
typedef pair<string, int> tt;
vector<tt> tab;
int licznik=0;
for(;;){ //odczyt
string str;
cin>>str;
if (str=="koniec") break;
tab.push_back(make_pair(str,++licznik));
}
//mięsko
sort(tab.begin(),tab.end());
auto it = unique(tab.begin(),tab.end(), [](const tt &a,const tt &b
) {return a.first==b.first;});
tab.resize( distance(tab.begin(),it) );
sort(tab.begin(),tab.end(), [](const tt &a,const tt &b ) {return
a.second<b.second;});
//i po mięsku.
for (int i=0;i<tab.size();i++)
{
cout<<tab[i].second<<" "<<tab[i].first<<endl;
}
return 0;
}
" [](const tt &a,const tt &b ) {return a.first==b.first;} "
to "lambda", stworzenie funkcji, która ma arguymenty jak w nawiasie ()
i robi to, co jest w nawiasie {}. Są one używane jako trzcie argument
unique (zeby sprawdzić, co traktujemy jako 'to samo' i sort)
Prościej być może byłoby wykorzystać pomysł A.L, wykorzystać jakiś
kontener asocjacyjny, set (drzewo binarne) albo unordered_ser (tablica
haszująca).
Ale to wszytko tylko, jeśli chcesz zachować oryginalną kolejność,
jeśli tylko wypisać bez powtórzeń, posortuj i postępuj jak post
wcześniej.
> Takie continue, tylko nieco dalej skaczące...
>> Widzę, że używasz c++, (znaczki <<). To czemu nie użyjesz
>> stringów.
>
> Tak jak wspominałem - musiałem napisać "jednorazówkę" do rozwiązania
> topornego zadania. Zanim program poczyścił zestawienia, wcześniej
> dokonywał operacji na pojedynczych znakach i tu było mi poręczniej
> użyć tablic. Zresztą, jak w zeszłym tysiącleciu przechodziłem z
> Pascala na C, strasznie irytował mnie brak zmiennej typu String,
> tylko te dziadowskie tablice znakow. Ale potem poczułem w tym pałera
> i trudno mi się znowu odkręcić. ;-)
Kto co lubi. Ale cięzko korzystać z nowych zabawek nie uzywając
std::string.
>> Tab to wtedy vector<string>.
>
> Abstrachuje Pan od układu odniesienia. ;-) Jestem "niedzielnym"
Ty też. To usenet, 'panowanie' najczęściej występuje tu w bardzo
zaawansowanej kłótni ;-)
> programista, a o tym czymś z klamerkami czytałem kiedyś może z raz u
> Grębosza... ;-) Rozkminienie tematu zajęłoby mi więcej czasu, niż
> rozwiązanie całego zadania - w zaoszczędzonym czasie wolę sobie
> popisać na usenecie. ;-)
Jakiś czas temu znajoma poprosiła mnie o przypomnienie jej c++.
Miała to na studiach (politechnika). Po 20 minutach zrobiła
wielkie oczy i zdziwiona rzekła: to tu da się pisać jak w normalnym
języku.
Te wszystkie zabawki pozwalają pisać łatwiej i szybciej.
Oczywiście, niestety, trzeba trochę czasu w ich poznanie zainwestować.
BTW. C i C++ to ambitny wybór do niedzielnego programowania;-)
pzdr
bartekltg
Następne wpisy z tego wątku
- 07.10.14 07:31 slawek
- 07.10.14 15:18 firr
- 10.10.14 15:28 M.M.
- 10.10.14 15:39 M.M.
- 10.10.14 16:01 bartekltg
- 11.10.14 10:07 M.M.
- 11.10.14 16:27 A.L.
- 11.10.14 17:31 M.M.
- 12.10.14 01:17 bartekltg
- 12.10.14 02:31 M.M.
- 12.10.14 12:52 M.M.
- 12.10.14 12:53 bartekltg
- 12.10.14 13:39 M.M.
- 12.10.14 17:25 bartekltg
- 12.10.14 19:53 M.M.
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-03 dziękuję nie tankuję
- 2024-06-03 Bo konie to ...
- 2024-06-03 narząd nieużywany zanika
- 2024-06-02 Restart PC-ta
- 2024-06-03 polskie miasta są małe
- 2024-06-04 Wrocław => Senior React Native Developer <=
- 2024-06-04 Warszawa => Sales Executive <=
- 2024-06-04 Białystok => ERP Implementer <=
- 2024-06-03 Zielona Góra => Engineer R&D Mechanic <=
- 2024-06-03 Kielce => UX/UI Designer <=
- 2024-06-03 Białystok => Inżynier DevOps Conexa First (Kontraktor) <=
- 2024-06-03 Warszawa => Technical Leader (Java Background) <=
- 2024-06-03 Warszawa => Senior Rust Software Engineer <=
- 2024-06-03 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=
- 2024-06-03 Marki => Senior PHP Developer <=