Lista - zadanie o więźniach i ich czapkach

witam, na wstepie chce zaznaczyc ze jestem kompletnym laikiem jesli chodzi o programowanie.ucze sie w c++.dostalam zadanie, a w zasadzie zagadke ktora zapewne kazdy zna-mianowicie chodzi o 100 wiezniow i ich czapki, celem jest zostaienie przy zyciu jak najwiekszej ich liczby.zrobilam to na tablicha, ponizej wkleje kod.moze nie jest to profesjonalne, ale dziala i o to mi chodzilo.musze na tej podstawie to samo zadanie zrobic na liscie.nie mam pojecia jak sie za to zabrac.prosze o pomoc napisania programu, ja i tlumaczenie kolejnych czynnosci wykonywanych na listach.

#include <sstream>
#include <cstdlib>
#include <iostream>
#include <string>
#include<ctime>


using namespace std;

int wypelnienie(int T[100])
 {

 srand ( time(NULL) );
for(int i=0;i<100;i++)
{
T[i]=rand() % 2;
}
for(int i=0;i<100;i++)
cout<<T[i]<<" ";
cout<<endl;
return 0;
 }
 
 int liczando(int T[100])
 {
 	
	 int i=0, j=0;
 	int suma=0, suma1=0;
    int czapki[100];
    
 	for(j=0;j<100;j++)
 	{
 	 suma=suma+T[i];	
 	}
 	
 	if(suma%2==0)
 	czapki[0]=1;
 	else
 	czapki[0]=0;
 	for(i=1;i<100;i++)
 	{
 		suma1=suma-T[i];
 		if(suma1<suma)
 		czapki[i]=1;
 		else
 		czapki[i]=0;
 		suma=suma-T[i];
 	}
 	for(j=0;j<100;j++)
 	{
 		cout<< czapki[j]<<" ";
 	}
 	cout<<endl;
 return 0;
 }
 
 int main()
 {
 	int T[100];
     cout<<"oto wiezniowie "<<endl;
    wypelnienie(T);
    cout<<"ilu przezylo? "<<endl;
	liczando(T);
 	return 0;
 }

może zbyt mało miałam do czynienia z takimi zadankami, ale ja nie znam. poza tym umieść kod w odpowiednie tagi i pisz jaśniej

jestem nowa na tym forum i nie za bardzo wiem jak to roic, z gory przepraszam

Strażnik proponuje dwudziestu więźniom następującą grę:
Więźniowie zostaną ustawieni w rzędzie w ten sposób, że pierwszy nie będzie widział pozostałych, drugi będzie widział tylko pierwszego, trzeci będzie widział tylko pierszych dwóch i tak dalej, ..., ostatni będzie widział pozostałych dziewiętnastu. Ustawionym w rządek więźniom strażnik nałoży na głowy kapelusze, każdy kapelusz będzie czarny lub czerwony. Następnie każdy więzień w rządku, w kolejności od ostatniego do pierwszego, oświadczy jakiego koloru jest jego kapelusz wypowiadając słowo "czarny" lub słowo "czerwony". Każdy więzień będzie słyszał wcześniejsze oświadczenia oraz będzie widział kapelusze więźniów stojących przed nim w rządku. Jakakolwiek inna komunikacja pomiędzy więźniami kończy się natychmiastową egzekucją całej dwudziestki.
Przed grą więźniowie mogą ustalić wspólną strategię, ich celem jest uratowanie jak największej liczby więźniów.
Jaka jest ta optymalna strategia i uratowanie ilu więźniów gwarantuje?

Oto zagadka.

Brakuje informacji kiiedy więzień jest zabijany - gdy poda zły kolor? Czy gdy ma dany (np. czerwony) kolor na głowie?

Anyway jeśli to ten z błędnym kolorem zginie, ten ostatni może podać kapelusz tego przed nim itd. Zawsze zginie tylko ten ostatni, bo reszta będzia znać kolory swoich kapeluszy od osób stojących za nimi.
Optymalna strategia.

EDIT: chyba, że ostatni akurat trafi i ma ten kolor, który osoba przed nim. Wtedy przeżyje dwudziestu.

Kiedyś słyszałem rozwiązanie tej zagadki na zasadzie powiedzenia słów "moja jest czerwona/czarna" jeżeli kolor czapki przed daną osobą jest różny od naszego lub po prostu "czerwona/czarna" jeżeli jest taki sam i wtedy maksymalnie jedna osoba ginęła (ostatnia) ale to tutaj nie pomaga, bo tutaj mogą powiedzieć tylko czerwona/czarna.

xfin napisał(a):

Brakuje informacji kiiedy więzień jest zabijany - gdy poda zły kolor? Czy gdy ma dany (np. czerwony) kolor na głowie?

Anyway jeśli to ten z błędnym kolorem zginie, ten ostatni może podać kapelusz tego przed nim itd. Zawsze zginie tylko ten ostatni, bo reszta będzia znać kolory swoich kapeluszy od osób stojących za nimi.
Optymalna strategia.

No nie, bo jak wiem, że mam czerwoną, a koleś przede mną ma czarną, to mam ratować siebie, czy jego?

Zadanie określa, że przed zaczęciem wyliczania, nikt nie wie jaki jest kolor jego czapki. Widzi tylko czapki gości z przodu.
Nie ma określonego, kiedy ktoś ginie (jak już xfin zauważył), ale można założyć, że wtedy gdy źle poda kolor swojej czapki.

Można uratować co najmniej dziesięciu więźniów. Ostatni więzień wypowie kolor czapki więźnia z przodu. Następnie ten więzień z przodu powtórzy ten kolor i dzięki temu będzie miał zagwarantowane, że powie dobrze. Następnie proces zostanie powtórzony dla każdej kolejnej pary i z każdej pary zostanie uratowany co najmniej jeden więzień.

Co robi Twoja funkcja liczando?
Nazywaj jakoś logicznie funkcje zmienne, bo ciężko się połapać

Rozwiązanie jest dość proste.

Oznaczamy jeden kolor 1, a drugi 0. Gość, który zaczyna sumuje wszystkie liczby przed nim i podaje wynik modulo 2 (czyli właściwie jest to XOR). Kolejny też liczy tę wartość i w przypadku, gdy jest taka sama to wie, że ma zero, jeśli jest różna to wie, że ma jedynkę. Trzeci i następni robią to samo: liczą sumę następnych modulo 2 (przyjmijmy n), liczą liczbę jedynek wśród wcześniej odpowiadających modulo 2 (przyjmijmy p), przypominają sobie co mówił pierwszy odpowiadający (przyjmijmy x) i na podstawie tego są w stanie ze stuprocentową pewnością określić swój kolor (k):
k+n+p mod 2=x

W najgorszym przypadku ginie tylko pierwszy odpowiadający, w najlepszym nikt.

Mam nadzieję, że nie namieszałem, rozwiazanie na szybko.

EDIT:
Np. dla takiego ciągu 1011101

-Pierwszy mówi 0, bo ma cztery jedynki przed sobą. Umiera.
-Drugi mówi, że 0, bo też ma parzystą liczbę jedynek czyli nie może mieć jedynki.
-Następny ma nieparzystą liczbę jedynek, a poprzednik miał parzystą czyli on ma jedynkę.
-nastepny
-Kolejny ma przed sobą parzystą liczbę jedynek, przed nim była jedna jedynka, a wcałym ciągu od drugiego do ostatniego ma być parzysta liczba jedynek więc ma jedynkę.
etc.

wiec tak.po pierwsze nie chodzilo mi o rozwiazanie teoretyczne zagadki bo do tego doszlam.chodzi mi o wykonianie tego na listach.moj algorytm dziala nastepujaco.funkcja wypelnienie wypelnia tablice stuelementowowa randomowo zerami i jedynkami.natomiast funkcja liczando najpierw liczy sume z tych naszych zer i jedynek.nastepnie ustala na tej podstawie czy jest parzysta liczba zer czy jedynek, jesli zer mowi zero jesli jedynek mowi jeden.ten pierwszy wiezien-element tablicy jest do stracenia .nastepnie robie petle ktora bedzie liczy sume1 czy sume kolejnych elementow od wybranego i potem porownuje ja z nasza stara suma.jesli ona sie zmienia znaczy ze dany wiezien musi byc 1 a jesli sie nie zmienia musi on byc zerem.

prosze o pomoc w przeniesieniu tego mojego algorytmu na liste

nie wiedza.dobra mam pytnie.wiec jak umiescic w liscie losowo zera i jedynki?

srand(time(NULL));
list <bool> lista;
for(int i=0;i<100;i++)
                 lista.push_back(rand()%2);

Najprościej do zrozumienia najmniej profesjonalnie ;/ ?

laik101 napisał(a):

nie wiedza.dobra mam pytnie.wiec jak umiescic w liscie losowo zera i jedynki?

Pomijając zasadność (a raczej jej brak) użycia listy, możesz to zrobić między innymi za pomocą biblioteki standardowej i std::generate lub std::generate_n, do losowości używając nagłówka <random>:

	std::mt19937 rd{std::random_device{}()};
	std::uniform_int_distribution<int> gen(0,1);

	list<bool> L1, L2;

	generate_n(back_inserter(L1), 10, bind(gen, ref(rd)));

	L2.resize(10);
	generate(begin(L2), end(L2), bind(gen, ref(rd)));

http://melpon.org/wandbox/permlink/ySbDxtBW9PLFvJsC

rand jest średnio bezpieczny i nie zaleca się jego używania.

na temat zasadnosci uzycia listy nie bede sie klocic, bo to nie moj pomysl.polecenie z gory;)

a tak łopatologicznie, po kolei jak zaimplementowac, wypelnic wyswietlic po kolei, kod z wyjasnieniem.naprawde nie mialam praktycznie w ogole doczynienie z listami.

laik101 napisał(a):

a tak łopatologicznie, po kolei jak zaimplementowac, wypelnic wyswietlic po kolei, kod z wyjasnieniem.naprawde nie mialam praktycznie w ogole doczynienie z listami.
Wypełnienie losowe masz wyżej.

Wyświetlenie jest jeszcze prostsze (zakładam, że masz listę nazwaną L1, tak jak w moim przykładzie wyżej):

for(bool val : L1){
	cout << val << ", ";
}

Jeśli Twój kompilator nie wspiera C++14 ani nawet C++11, to natychmiast go zmień. Jeśli nie możesz, to jedyną sensowną metodą jest:

for(list<bool>::const_iterator it = L1.cbegin(), e = L1.cend(); it != e; ++it){
	cout << *it << ", ";
}

a jakie biblioteki beda mi potrzebne?

nie rozumiem za bardzo jak to zrobic,jak normalnie implementuje liste i robie po kolei powyzsze to mi jakies dziwne errory wyskakuja w devc++

Nie znam się na devc++, ale nie jest on nierozwijany i przez to ma "wbudowany" stary kompilator, który nie obsługuje standardów podanych przez @kq

laik101 napisał(a):

nie rozumiem za bardzo jak to zrobic,jak normalnie implementuje liste i robie po kolei powyzsze to mi jakies dziwne errory wyskakuja w devc++
Ty implementujesz listę? Chyba mylisz użycie z implementacją. Dev-cpp to przestarzałe świństwo, którego już nikt nie powinien używać. Chyba, że mowa o wersji orwell, ale i od tego są znacznie lepsze środowiska (Qt Creator, Code Blocks, KDevelop, MSVS...)

A co do errorów, moja szklana kula do października jest nieczynna, musisz podać ich treść oraz kod, który je powoduje :/

Myślę, że on implementuje liste i próbuje użyć petli for each. Jeśli zrobiłeś własną liste to:

srand(time(NULL));
Lista list;
for(int i=0;i<100;i++)
                 list.dodaj(rand()%2);

prosze o kod tego zadania z wyjasnieniem, bo tak po kawalku nie zrozumiem.a na tym przykladzie chcialabym zrozumiec wykorzystanie i mozliwosci list.z gory badzo dziekuje

http://pl.wikibooks.org/wiki/C++/Listy

for(i=1;i<100;i++)
     {
         suma1=suma-T[i];
         if(suma1<suma)
         czapki[i]=1;
         else
         czapki[i]=0;
         suma=suma-T[i];
     } 

jestem w tym momencie ojego kodu na tablicach.mam w zwiazku z tym pytanie.jak w liscie ustawic poczatkowo iterator w drugim elemencie?

iterator i=lista.begin();
++i;

Ten kod z postu wyżej można zastąpić na:

for(i=1;i<100;suma-=T[i++]) czapki[i]=(T[i]>0);

no dobrze ale mi chodzi o sam ten moment

for(i=1;i<100;i++)

ja chce to zrobic na liscie ten sposob ze nie zaczne od elementu lista.begin() ale od elementu nastepnego

dodanie znacznika <code class="cpp"> - furious programming

next(begin(list))

http://melpon.org/wandbox/permlink/WwJK4ftOp222R0lJ

jak wyżej lub:

for(iterator ii=lista.begin(),i=++ii;i!=lista.end();++i)

suma1=suma-T[i];
         if(suma1<suma)
         czapki[i]=1; 

dobra teraz dalej.jak zapisac i-ty element listy?zeby wykonac roznice pomiedzy nim i suma?oraz przypisywac i-tym elementom odpowiednia wartosc?