Nuputamiseks: Paberi voltimine

Question

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 A₁,A₂,...,A_N.

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.

Accepted Answer

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
____
  ____

Answer 2

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

Answer 3

0

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
3●3

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 ♦♦

Answer 4

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); ?>

Nuputamiseks: Paberi voltimine

Jälgi seda küsimust

Pinu tööpakkumised

Sarnased küsimused