Názory ke článku Google Code Jam 2008 - cvičení – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Názory ke článku Google Code Jam 2008 - cvičení – Programujte.comNázory ke článku Google Code Jam 2008 - cvičení – Programujte.com

 

Názory ke článku Google Code Jam 2008 - cvičení

luky   NOVÝ
10. 8. 2008

Jakube, nic moc. Pricitam to Vasemu zvyku psat tak, aby chapali i idioti :)

dejvik   NOVÝ
10. 8. 2008

luky: O zvyku nic nevim, ale me se zda prave naivni popis uloh vhodny pro prilakani lidi, kteri nikdy neresili programovaci ulohy :) Pekny clanek.

djanosik   NOVÝ
10. 8. 2008

Reagoval na komentář od uživatele dejvik : Mám na to stejný názor. Zdejší obsah nemusí být jen pro pokročilé čtenáře.

Michal   NOVÝ
12. 8. 2008

Tak treba ten problem s vajicky neni moc dobre popsany a na uvedenem odkazu jsem zadani nenasel:(

Podle toho zadani zde vubec nevim, proc mam nektera vajicka, kdyz je stejne nemuzu rozbit, a kdyby ten problem byl takovy, jak je tu popsano, tak bych postupoval binarnim pulenim a pocet pater budovy by byl 2^pocet vajicek

Architekt   NOVÝ
13. 8. 2008

Doporučoval bych pro příště psát takové články ve stylu Matematického koutku tady na programujte, kdy je srozumitelně zadaná nějaká úloha, není předem prozrazeno řešení a zájemci odevzdávají svá řešení v úkolech. Správné řešení je pak prozrazeno v dalším díle.

Co se týče těchto úloh, zaujala mě ta vajíčka. Koukal jsem na originální zadání a oproti tvému řešení jsem nejdřív zkusil vymyslet ten algoritmus házení vajíček, protože bez něj nelze úlohu řešit. Jako nejefektivnější se mi pro tyto účely jeví metoda půlení intervalu (binární půlení). A když víme, jak funguje, stačí jednoduchá matematika základní školy ke spočítání správného řešení.

Moje řešení v Pythonu (dle originálního zadání, pro zde uvedené zadání stačí pouze fce Fmax):

#!/usr/bin/env python

# -*- coding: utf-8 -*-

import math

def Fmax(D, B):
"""
Vrací maximální počet pater budovy.
D = celkový počet vajíček
B = počet vajíček které můžeme rozbít
"""
# zde je třeba si uvědomit, že v případě, kdy dojde k rozbití
# maximálního počtu vajíček (když se nerozbíjí pouze v prvním
# patře) stačí celkem (D) jen o jedno vajíčko více, než je počet
# k rozbití (B)
if D > B+1:
D = B+1
# omezení z původního zadání, kdy pro řešení >= 2^32 je výsledek
# vždy -1
if D >= 33:
return -1
else:
# a tohle je řešení :-)
return 2**D - 1

def Dmin(F):
"""
Vrací minimální počet vajíček potřebných pro řešení.
F = zadaný počet pater
"""
return int(math.log(F + 1, 2))

def Bmin(F):
"""
Vrací minimální počet vajíček které můžeme rozbít.
F = zadaný počet pater
"""
return Dmin(F) - 1

# teď už těmi funkcemi stačí jen prohnat testovací data

vrana   NOVÝ
13. 8. 2008

Reagoval na komentář od uživatele Architekt :

Články oproti soutěži vycházejí se značným zpožděním, takže si je zájemci mohou vyřešit nezávisle a s články následně jen porovnat. Psát článek jenom jako přesný překlad zadání by mě nebavilo.

Úloha se zjevně dá řešit i bez znalosti algoritmu, jak dokazuje můj postup.

Půlení intervalu je pro tuto úlohu nedostačující postup. Stačí si představit řešení např. pro celkem 3 vejce, z nichž se 2 dají rozbít. Optimální postup je tento:
[seznam]Začnu ve třetím patře. Když se vejce rozbije, jdu do prvního, jinak do pátého.[/seznam]
[seznam]Když se rozbije v prvním, jsem hotov, jinak jdu do druhého.[/seznam]
[seznam]Když se vejce rozbije v pátém, jdu do čtvrtého, jinak do šestého.[/seznam]
Výsledek je tedy ten, že se dá prozkoumat šest pater. Algoritmus se od půlení intervalů zásadně liší.

Pokud stále nevěříte, tak své výsledky zkuste poslat a uvidíte, že jsou špatně. Např. pro 20 vajec, z nichž lze 5 rozbít, se dá prozkoumat 21699 pater, i když váš algoritmus tvrdí 63.

Architekt   NOVÝ
13. 8. 2008

Reagoval na komentář od uživatele Architekt :

Tak beru zpět co jsem napsal. Koukal jsem na řešení na netu a zjistil jsem že v závislosti na rozdílu mezi D a B je možné začít házet ne v půlce, ale v nižších patrech (a stejně tak přizpůsobit i další hody) a pak se dá prozkoumat vyšší barák.

vrana   NOVÝ
13. 8. 2008

Reagoval na komentář od uživatele Architekt :
Jak by jen pro zajímavost vypadal algoritmus pro 20 vajec, z nichž lze 5 rozbít:
[seznam]Začnu v 5036. patře. Když se vejce rozbije, jdu do 988. patra, jinak do 9084.[/seznam]
[seznam]...[/seznam]
[seznam]Když se vejce rozbije v prvním patře, jsem hotov. Když se nerozbije v 21698. patře, jdu do 21699.[/seznam]

pa3k   NOVÝ
15. 8. 2008

Gratulujem! (portálu)

Přidej svůj názor

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo e-mailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Reaguješ na příspěvek:
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové názory e-mailem (pouze pro přihlášené)
Sleduj názory ke článku a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.



Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý