Moneta o większej wadze

Question

Witam. Myślę od kilku dni nad pewnym zadaniem, niestety mój mózg jest na to zbyt mały. Chodzi o pewne zadanie, które polega na podaniu najmniejszej liczby kroków (x) które trzeba zrobić, aby znaleźć fałszywkę wśród n monet. Wejście:n, wyjście: x. Dalej nie wiem co mnie w tym przerasta. A jednakmój program działa tylko w połowie przypadków. Po prostu nie mogę znaleźć w głowie ani po rozpisaniu przypadków w których "algorytm" nie działa.

Mając do dyspozycji
wagę szalkową znajdź fałszywą monetę w jak najmniejszej liczbie ważeń. W sumie, wystarczy, że podasz
liczbę ważeń potrzebną w najgorszym przypadku.

Na przykład wśród 10 monet, fałszywkę można znaleźć w 3 ważeniach:
1. w pierwszym ważeniu dzielimy monety po połowie na obie szalki, jedna z szalek opadnie, więc wśród
tych pięciu monet jest ta cięższa,
2. w drugim ważeniu kładziemy po dwie monety na lewej i prawej szalce, a piątą monetę kładziemy obok
wagi. Gdy szalki będą na równym poziomie, to właśnie ta moneta była najcięższa. Ale to nie byłby
najgorszy przypadek, więc możemy przyjąć, że waga wskazała cięższą parę monet,
3. w trzecim ważeniu sprawdzamy, która z dwóch pozostałych monet jest cięższa. To ona jest fałszywa.
Można udowodnić, że w przypadku 10 monet nie da się wykryć fałszywej w mniej niż trzech ważeniach

 

//////////////////////////

 

Ja mam świadomość, że nie powinienem się tu błaźnić z takim pytaniem, ale problem jest bardziej matematyczny niż informatyczny. Dzięki z góry za pomoc.

Answer 1

Kodu ci nie napiszę (bo to nie ładnie podpowiadać), ale mogę pomóc pod względem logicznym i  algorytmicznym ;)
1)Zauważ że gdy mamy parzystą liczbę monet to jeden ze stosików będzie cięższy. Wtedy przedzielamy go na pół i znów ważymy
Rys.
oooO > oooo
oo < oO
o < O
2) Gdy mamy nieparzystą liczbę zabieramy jedną monetę ze stosiku, dzielimy pozostałą część na 2 i mamy dwa możliwe przypadki:
a) stosiki będą równe - wtedy zabrana moneta jest cięższa
Rys.
ooo = ooo i O
b) jeden ze stosików będzie cięższy - wtedy tak jak 1)
Rys.
oo <oO i o
o < O

Czyli dla np 17:
zabieramy jedną monetę i ważymy stosiki monet

O+7*o > 8*o i pozostałe o
O + 3*o > 4*o
O + o > o+o
O > o

Czyli przechodząc do algorytmu:
Albo robisz to rekurencyjnie, albo w pętli. Jeśli masz liczbę nieparzystą to odejmujesz 1 i dzielisz przez 2. Jeśli parzystą dzielisz przez 2. LIcząc ilość podziałów masz wynik.

P.S. W najlepszym przypadku liczba ważeń wynosi 1 ;)

Comments

Wszystko się zgadza tylko po co te pętle albo rekurencje? Wystarczy wyciągnąć logarytm.

---

Wiem, co to logarytmy. Oczywiście zrobiłem tak na początku, daje mi to wynik=0, na testach tylko ok. 5% jest dobrze, ale wciąż jest to wynik 0 pkt.

Answer 2

#include <iostream>
#include <cmath>

using namespace std;

int main () {
    int n;
    cin >> n;

    if (n>3) cout << floor(log2(n));
    else cout << 1;

    return(0);
}

Rozwiązanie jest banalne. Potęgujesz liczbę 2 tak długo aż nie przekroczysz liczby n. Czyli dla n=10 to jest 2^3 (dwa do potęgi 3) bo 2^4 już przekracza 10. No i wynikiem jest właśnie ta potęga, czyli w tym przypadku 3.

Comments

Ja i ty rozumiemy logarytmy. On może niekoniecznie. Wytłumaczyłem tak, aby osoba czytająca niezależnie od wieku mogła to zrobić i zrozumieć

---

Wiem, co to logarytmy. Oczywiście zrobiłem tak na początku, daje mi to wynik=0, na testach tylko ok. 5% jest dobrze, ale wciąż jest to wynik 0 pkt.

---

Masz rację, ten algorytm nie jest doskonały.  Można to zrobić mniejszą ilością ważeń. Już wiem jak, ale zrobiłem sobie właśnie przerwę w grillowaniu, wieczorem wszystko wyjaśnię ;) Tak na szybko tylko powiem że chyba floor(log2(n) trzeba zastąpić floor(log3(n)) ale przemyślę to i napiszę później bo jestem po kilku piwkach.

---

No to już widać, że w moim wypadku, żeby zrobić zadanie trzeba bylo się właśnie piwa napić :) A nawet czterech.

Jest tak jak mówisz. I co ja mam teraz powiedzieć żeby nie było, że zainspirowałem się twoim komentarzem? No nie wiem. Znaczy ja zrobiłem to od drugiej strony, ale w sumie tak samo, po prostu na początku sprawdzałem której potęgi liczby trzy liczba n jest najbliżej, ale jednocześnie jest od niej mniejsza, potem już tylko wyciągnąłem logarytm.

 
Jak tak dłużej pomyślę to dochodzę do wniosku, że do tego służyła ta instrukcja floor :) Pozdrawiam.

---

Dobra więc tak... Wypiłem już za dużo żeby napisać jakikolwiek program ale podsunę pomysł. Jutro na trzeźwo program zrobię. Przed ważeniem trzeba podzielić nie na 2 części tylko na 3. Jak na wadze wyjdzie że obie są równe to fałszywa moneta jest w trzeciej części.  I teraz problem jest taki że np przy 16 mamy dwie równe części na wagę a trzecia część zostaje do sprawdzenia. Przy 17 mamy 2 x po 6 szt na wagę i 5 szt jako trzecia część. I teraz wystarczy dobrać jakiś wzór do tego. Niestety na razie nie jestem w stanie. Rano pomyśle o tym o ile sam tego wcześniej nie zrobisz. Pozdrawiam

---

Już zrobiłem, kluczem były potęgi trójki. Ale po Twoim poście widzę jak wielką pasję mają ludzie tutaj. Sam w tym momencie po 6 Kuflowych ledwo zdobyłem motywację żeby cokolwiek napisać, a Tobie chciało tłumaczyć się zagadkę matematyczną po większej ilości :) Dziękuję i pozdrawiam.

 

A to o czym mówisz pisałem ze zdziwieniem w komentarzu do pierwszej odpowiedzi do tego tematu (ktoś proponował właśnie log2(a)), niestety ktoś chyba usunął post :( Problem miałem właśnie z algorytmem bo byłem przekonany że chodzi o modulo 3. Chociaż przyznam szczerze, że na początku sam robiłem odpowiednik waszych propozycji z log2(a), ten przykład w zadaniu jest okropnie chamsko napisany. Dziękuję i dobrej nocy.

---

U mnie to nie była większa ilość bo jak rano policzyłem to było akurat 5 kuflowych ;) Z tym że po czterdziestce na karku to robi już różnicę ;) Jak program napisałeś to już nie będę dalej rozkminiał. Życzę powodzenia i polecam zadania ze spoja.