logi sisse meist KKK
4
2

Matil on pabeririba, mis koosneb N ühesugusest ruudukujulisest lahtrist. Ta kirjutab lahtritesse vasakult paremale arvud 1...N ja murrab riba kokku nii, et tulemuseks on ühe lahtri suurune ja N kihi paksune pakk. Seejärel väidab ta, et pakis ülalt alla lugedes on arvud järjekorras A1,A2,...,AN.

Kirjutada programm, mis kontrollib, kas see väide võib tõele vastata.

Näide: 3,1,2,4 --> jah (selline tulemus tekib, kui riba vasakult paremale kokku "rullida").

Näide: 1,3,2,4 --> ei.

Näide: 1,4,3,2 --> jah (selline tulemus tekib, kui murda riba pooleks paremalt vasakule ja tulemus uuesti pooleks vasakult paremale).

Näide: 2,3,4,1 --> jah (selline tulemus tekib, kui pärast eelmise näite voltimist pakk kummuli keerata).

PS. See on meelelahutus, mitte küsimus, mille vastust mulle millekski tegelikult vaja oleks.

küsitud Jan 02 '10 at 01:51

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

edited Jan 02 '10 at 01:59

Kas näide 1 on korrektne?

(Jan 05 '10 at 21:52) sigamozart

Peaks olema küll. Alguses on 1,2,3,4. Esimese voltimisega läheb 1 kummuli 2 peale, saame (1,2),3,4. Teise voltimisega läheb (1,2) kummuli 3 peale, saame (2,1,3),4. Kolmanda voltimisega läheb (2,1,3) kummuli 4 peale, saamegi (3,1,2,4).

(Jan 06 '10 at 06:53) Ahto Truu ♦♦

Okih, ei viitsinud ära optimiseerida... aga töötab:

import List
import Data.Maybe

intersected _ [] = False
intersected x@(a,b) ((c,d):xs) = 
    ((a < c) && (c < b) && (b < d)) || 
    ((c < a) && (a < d) && (d < b)) ||
    intersected x xs

isNotFoldedRec x up down idx
    | idx >= length(x) = False
    | otherwise = 
        let (a,b) = (fromJust (elemIndex idx x), fromJust (elemIndex (idx+1) x))
            t = if a < b then (a,b) else (b,a)
        in  intersected t up || isNotFoldedRec x down (t:up) (idx + 1)

isFolded x = not $ isNotFoldedRec x [] [] 1

Seletus:

Alustame voltimist number ühest

 /\
1  2

Voldime number 3. juurde
            ___
 /\        /   \     
1  2  3   1  3  2 
    \/        \/  

Ja 4.
               ___
 /\    /\     / - \     
1  2  3  4   1  3  2
    \/           \/

On ilmne, et läbi paberi teist paberit panna ei
saa, siis parempoolsele näitele 4 juurde ei saa voltida...

Samuti on lihtne näha, et murde koht vaheldub pidevalt,
üles ja alla. Ehk joonistame murde joone 6,2,3,4,1,5-le.
___________
| _______ |
| | ___ | |
| | | | | |
6 2 3 4 1 5
  |_| |___|

Kuna paber ennast ei lõika, siis on selline voltimine võimalik.

Ehk, kas murretele 
ülemised: (1,2) (3,4) (5,6)
alumised: (2,3) (4,5)

vastavad murde-"intervallid"
ülemised: (1,4) (2,3) (0,5)
alumised: (1,2) (3,5)

on mitte lõikuvad, ehk 
____              _______
      ____  või     ___

aga mitte
____
  ____
link

vastatud Feb 26 '10 at 13:05

egon's gravatar image

egon ♦♦
771239

edited Feb 28 '10 at 14:22

Lahendus mis esmalt tuli meelde: haruta voltimistee lahti.

Programm:

public boolean isFlipAble(Integer[] nrs) {
	int min = 0, max = nrs.length - 1;
	return isFlipAbleMin(nrs, min, max, min)
			|| isFlipAbleMax(nrs, min, max, max);
}

private boolean isFlipAbleMin(Integer[] nrs, int down, int up, int i) {
	if (down >= up) return true;

	if (nrs[down] == i + 1)
		return isFlipAbleMin(nrs, down + 1, up, i + 1);
	if (nrs[up] == i + 1)
		return isFlipAbleMin(nrs, down, up - 1, i + 1);

	return false;
}

private boolean isFlipAbleMax(Integer[] nrs, int down, int up, int i) {
	if (down >= up) return true;

	if (nrs[down] == i + 1)
		return isFlipAbleMax(nrs, down + 1, up, i - 1);
	if (nrs[up] == i + 1)
		return isFlipAbleMax(nrs, down, up - 1, i - 1);

	return false;
}

Ning kasutamiseks nt:

public flip() {
	System.out.println(isFlipAble(new Integer[] { 3, 1, 2, 4 }));
	System.out.println(isFlipAble(new Integer[] { 1, 3, 2, 4 }));
	System.out.println(isFlipAble(new Integer[] { 1, 4, 3, 2 }));
	System.out.println(isFlipAble(new Integer[] { 2, 3, 4, 1 }));
}

public static void main(String[] args) {
	new flip();
}

Tulem:

true
false
true
true
link

vastatud Jan 24 '10 at 18:15

Margus's gravatar image

Margus
51116

System.out.println(isFlipAble(new Integer[] { 6, 2, 3, 4, 1, 5 })); ütleb false, aga tegelikult saab küll sellise tulemuse voltida: alguses on 1,2,3,4,5,6; voldime vasakult 1,2 kummuli 3,4 peale, saame (2,3),(1,4),5,6; voldime vasakult paremale pooleks, saame (4,1,5),(3,2,6); nüüd voldime paremalt vasakule pooleks, saamegi (6,2,3,4,1,5).

(Jan 24 '10 at 19:13) Ahto Truu ♦♦

Voltisin natuke paberit. Testisin täpselt 2-e paberi ribaga, st. võin eksida. Kas võib olla, et lahendus kontrollimiseks on umbes selline:

pseudocode:
              G = new Graph(size, size);
              G.AddEdge(A1, A2);
              G.AddEdge(A2, A3)
              G.AddEdge(A3, An)...;
              if(Path(A1, ...An) == IsEulerian)
                  return true;
link

vastatud Jan 27 '10 at 10:46

blinx's gravatar image

blinx
313

Eee... Kas ma saan õigesti aru, et mõte on teha N tipuga graaf (üks tipp iga lahtri kohta) ja panna sinna N-1 serva (üks serv iga lõppjadas kõrvuti oleva lahtripaari kohta)? See ei saa kindlasti lahendus olla, sest selliselt saadud graafi servad moodustavad konstruktsiooni põhjal alati Euleri ahela ja seega ei ole sellelt lahenduselt kunagi võimalik saada vastust "ei".

(Jan 27 '10 at 18:38) Ahto Truu ♦♦

läksin lihtsamat teedpidi, kõikide variantide läbiproovimine. pole jah just kiireim lahendus aga ei suutnud midagi paremat välja mõelda :P

<?php
function flip($array, $from, $to, $direction = 0)
{
    $elements = ($from + $to + 1);
    if($elements % 2 != 0)
     return array();
     
     $elements /= 2;
     if($from != 0)
     {
         $r = count($array); 
         for($i = $from - 1, $j = 1; $i >= 0; $i--, $j++)
             if($j + $to + 2 >= $r)
              break;
              
         $from = $i;
         $to += $j;
     }

    for($i = 0; $i < $elements; $i++)
    {
        $from_elems = array_reverse((array)$array[$from + $i]);
        $to_elems = $array[$to - $i];    
        $array[$to - $i] = 
         !$direction ? array_merge((array)$from_elems, (array)$to_elems)
             : array_merge((array)$to_elems, (array)$from_elems);
    }
    for($j = $from - 1; $j >= 0; $j--)  array_push($array, $array[$j]);
    for($i = 0; $i < $elements; $i++)   array_shift($array);
    return $array;
}

function bruteforce($set, $searching_for)
{
  if(count($set) <= 1)
  {
    if($set[0] == $searching_for)
     echo "Jah on võimalik teha seda <br>";
    return;
  }
    
  for($i = 1; $i < count($set); $i += 2)
  {
    bruteforce(flip($set, 0, $i, 0), $searching_for);
    bruteforce(flip($set, 0, $i, 1), $searching_for);
  }
}

$start = microtime();
$input = array(1, 3, 2, 4);
bruteforce(range(1, max($input)), $input);
echo "<br> Programm võttis ". (microtime() - $start)." mikrosekundit";
echo highlight_file(FILE);
?>

link

vastatud Feb 28 '10 at 17:44

erti%202's gravatar image

erti 2
71347

Koodi võiks ikka vahele panna. Need "$" on PHP keele syntaxi puhul äärmiselt häirivad, vähemalt minu jaoks, aga kuidas kellegile.

(Feb 28 '10 at 20:38) Timo
Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×7

küsitud: Jan 02 '10 at 01:51

nähtud: 6,239 korda

viimati uuendatud: Mar 05 '10 at 18:04

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee