logi sisse meist KKK
2
1

Ülesanne: kirjutada funktsioonid, mis leiavad ringpuhvris olevas kasvavalt järjestatud arvujadas
a) minimaalse väärtusega elemendi;
b) antud väärtusega elemendi.

Ringpuhver on massiiv, mille esimest elementi loetakse viimasele järgnevaks. Kasvav arvujada ringpuhvris a[1..n] tähendab, et mingi i (kus 1 <= i <= n) korral kehtib: a[i] <= a[i+1] <= ... <= a[n] <= a[1] <= ... <= a[i-1].

Vastavalt kasutatavale keelele võib eeldada massiivi a[1..n] või a[0..n-1].

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

PPS. Väidetavalt kasutab Google seda küsimust oma programmeerijakandidaatide sõelumiseks.

küsitud Nov 14 '09 at 00:48

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

Paar näidet oleks hea.

(Nov 14 '09 at 09:12) Rene Saarsoo ♦♦

FindMin([5,6,7,1,2,3,4]) --> 4 (või 3, kui indeksid on nullist)

(Nov 14 '09 at 15:40) Ahto Truu ♦♦

FindVal([5,6,7,1,2,3,4], 2) --> 5 (või 4, kui indeksid on nullist)

(Nov 14 '09 at 15:41) Ahto Truu ♦♦

Ahjaa, väärtused ei tarvitse muidugi alati olla 1..n:
FindMin([7,9,2,4]) --> 3 (või 2, kui indeksid on nullist)

(Nov 14 '09 at 15:42) Ahto Truu ♦♦
1

Ma olen natuke üllatunud, et ei tulnud ühtegi lahendust, mis oleks lähtunud tähelepanekust, et massiivi algusest kuni miinimumini on üks ja miinimumist massiivi lõpuni teine mittekahanev lõik. Otsitava väärtuse ja massiivi esimese elemendi võrdlemise põhjal oleks kohe teada, kummas neist kahest otsitav element olla võiks. Siis saaks FindVal realisatsioonis FindMin abil miinimumi asukoha leida ja sealt edasi juba puhast kahendotsingut kasutada.

(Nov 25 '09 at 13:31) Ahto Truu ♦♦

12järgmine leht »

Ma pakun välja järgmise lahenduse

function FindMinElement(const A: array of Integer; const L, R: Integer): Integer;
var
  M: Integer;
begin
  M := (L + R) div 2;
  if L = R then
    Result := M
  else if A[R] < A[M] then
    Result := FindMinElement(A, M + 1, R)
  else
    Result := FindMinElement(A, L, M);
end;

function FindElement(
  const A: array of Integer; const L, R: Integer; const X: Integer): Integer;
var
  M: Integer;
begin
  M := (L + R) div 2;
  if A[M] = X then
    Result := M
  else if A[M] < A[R] then begin
    if (A[M] < X) and (X <= A[R]) then
      Result := FindElement(A, M + 1, R, X)
    else
      Result := FindElement(A, L, M - 1, X);
  end else begin
    if (A[M] < X) or (X <= A[R]) then
      Result := FindElement(A, M + 1, R, X)
    else
      Result := FindElement(A, L, M - 1, X);
  end;
end;
link

vastatud Nov 14 '09 at 15:22

Avo's gravatar image

Avo
12014

Kogu austuse juures pean ma ütlema seda, et need ühetähelised muutujad ajavad mul pea täiesti segi.

(Nov 15 '09 at 11:56) Rene Saarsoo ♦♦

PHP-s

function find_min_element($arr) {
  $count = count($arr);
  $min = $arr[0];
  for($i=1;$i<$count;$i++) {
    if ($min > $arr[$i]) {
      $min = $arr[$i];
      $res = $i;
      break;
    }
  }
  return $res;
}

function find_element($arr,$el) {
  $count = count($arr);
  for($i=0;$i<$count;$i++) {
    if ($el == $arr[$i]) {
      $res = $i;
      break;
    }
  }
  return $res;
}
link

vastatud Nov 14 '09 at 18:56

Jaan%20J's gravatar image

Jaan J
213

edited Nov 16 '09 at 20:42

find_element() võiks lõpetada töö kohe kui vastus käes. find_min_element() muutuks tibake effektiivsemaks kui >= asemel kasutada lihtsalt >.

(Nov 15 '09 at 11:49) Rene Saarsoo ♦♦

Ning function on üldiselt kombeks kirjutada ikka väikse algustähega, et mitte ajada seda segamini klassinimedega, mida on kombeks suure tähega alustada.

(Nov 15 '09 at 11:51) Rene Saarsoo ♦♦

probleemid parandatud :)

(Nov 16 '09 at 20:47) Jaan J

+1 selle koodi hallatavuse (maintainability) eest - suvaline programmeerija on võimeline 10 sekundiga tuvastama, mida see kood teeb ja kuidas teda muuta, nii et see katki ei lähe. Lisaks kasutab see mälu O(1) võrrelduna rekursioonipõhiste lahendustega, mis kasutavad mälu O(log2n) (pinu! :) (ärge tapke kui siin millegagi mööda panin). Lõpuks nende andmemahtude puhul, kus lineaarse otsingu ja kahendotsingu ajaline vahe märkimisväärseks kujuneb, on minu meelest lahenduseks mingi kavalam andmestruktuur, kuna andmed on niikuinii kõvakettal.

(Nov 17 '09 at 07:47) Tambet Matiisen ♦♦
1

Koodi hallatavuse koha pealt ma olen nõus. Antud juhul on sul mälu keerukuse koha pealt ka õigus, aga need rekursiooniga töötavad lahendused saab iteratiivseks teha ilma stackita, st ka mälu kuluks saab O(1). Ise realiseerin rekursiivselt ainult loetavuse huvides. Mis andmemahtudesse puutub, siis 1k suuruse ringpuhvri korral on lg n lahendus 100 korda kiirem (reaalselt märksa vähem) ja kui puhvrist massiliselt päringuid tehakse, siis juba see suur vahe.

(Nov 17 '09 at 11:47) Avo

@Jaan: Koos parandustega tekitasid find_min_element() funktsiooni vea.

(Nov 17 '09 at 21:05) Rene Saarsoo ♦♦

@Rene Aga palun õpeta mind noort inimest. Copy-pastega funktsioon töötab.

(Nov 18 '09 at 07:59) Jaan J

@Jaan: Ahh.. minu viga. Unustasin ära, et need asjad on seal ringpuhvris ju kasvavalt järjestatud. Varem töötas su kood ka suvaliselt järjestatud massiivist miinimumi leidmiseks, aga ülesanne seda muidugi ei nõua.

(Nov 18 '09 at 20:05) Rene Saarsoo ♦♦

Peab mainima, et Tambeti kiidetud iseenesest-mõistetavus langes tublisti selle brake; lisamisega find_min_element funktsiooni, sest nüüd pole enam võimalik ilma konteksti teadmata aru saada, miks funktsioonist selle koha peal ühtäkki väljutakse.

(Nov 18 '09 at 20:08) Rene Saarsoo ♦♦

Vabandan kommentaaride puudumise ja üritan tulevikus end parandada.

(Nov 18 '09 at 20:25) Jaan J
näitan 5/10 näita kõiki

Kuna tegemist Googli küsimusega, siis läksin kaasa viimase hullusega ning kirjutasin lahenduse Go keeles.

Kummagi funktsiooni puhul kasutatakse natuke modifitseeritud varianti kahendotsingust. Seega kumbki peaks halvimal juhul olema O(log(n)).

Täiesti suurepäraselt sobisid selle ülesande jaoks Go tükid (slice), mis võimaldavad effektiivselt anda funktsioonile edasi valitud tükikese massiivist. Näiteks kui allolevas koodis on array[0:m] siis mitte ei looda uut massiivi, mis sisaldab vana massiivi elemente 0 kuni m-1, vaid luuakse justnagu alammassiiv, mis teab et ta on osa sellest suurest massiivist, kuid käitumise poolest on see justnagu päris massiiv, välja arvatud, et kui sa sellele omistad, siis muutuvad ka alloleva massiivi elemendid.

package main

import "fmt"
import "math"

// Returns two values:
// - index of the needle
// - true on success, false when not found
func find(array []int, needle int) (int, bool) {
    length := len(array);

    // When empty array, then not found.
    if length == 0 {
        return 0, false
    }

    // Find the middle of the array
    m := length / 2;

    // remember the beginning and end of first half of the array
    begin := array[0];
    middle := array[m];

    switch {
    // Answer found when needle at the beginning or middle of array
    case begin == needle:
        return 0, true
    case middle == needle:
        return m, true

    // When first half is sequencial and contains needle
    case begin < needle && needle < middle:
        return find(array[0:m], needle)

    // When first half not sequencial and contains needle
    case begin > middle && (needle > begin || needle < middle):
        return find(array[0:m], needle)
    }

    // Otherwise must be in second half.
    index, ok := find(array[m+1:length], needle);
    return index + m + 1, ok;
}

// Returns index of smallest array element
func min(array []int) int {
    length := len(array);

    // We know the answer for 1..2 element arrays
    if length <= 2 {
        if length == 1 || array[0] < array[1] {
            return 0
        } else {
            return 1
        }
    }

    // We also know the answer when the whole array is
    // sequentially sorted
    if array[0] < array[length-1] {
        return 0
    }

    // Find the middle index of the array
    m := length / 2;

    // The smallest element must be in this half of array
    // that is not sequencially sorted.

    // Is the first half non-sequencial?
    if array[0] > array[m] {
        return min(array[0 : m+1])
    }
    // So it must be the second half.
    return m + min(array[m:length]);
}

func main() {
    arr := []int{5, 6, 7, 9, 10, 1, 2, 3, 4};
    needle := 3;

    index, ok := find(arr, needle);
    if ok {
        fmt.Printf("Found at %d\n", index)
    } else {
        fmt.Printf("Not found\n")
    }

    fmt.Printf("Minimum at %d\n", min(arr));
}
link

vastatud Nov 15 '09 at 11:18

Rene%20Saarsoo's gravatar image

Rene Saarsoo ♦♦
1.1k101121

edited Nov 26 '09 at 19:06

Mulle tundub alati kahtlane, kui massiivi indeksiteks hakatakse reaalarve panema. Pakun, et int(math.Ceil(float64(length / 2))) asemel oleks parem kasutada (length + 1) / 2.

(Nov 25 '09 at 13:16) Ahto Truu ♦♦
1

Pealegi, kui length on täisarv, siis on kõigis mulle tuntud keeltes paaritu length korral length / 2 juba allapoole ümardatud ja selle hilisem reaalarvuks teisendamine kaduma läinud .5 enam tagasi ei too. Pole küll kindel, kas see ümardamise suund üldse on lahenduse jaoks oluline, aga näha on, et selle nimel on tulutult vaeva nähtud ;)

(Nov 25 '09 at 13:20) Ahto Truu ♦♦

Õige märkus. Nüüd takkajärgi ei saa ma enam ise ka aru, mida ma selle ümardamisega saavutada tahtsin. Aga noh... kell oli umbes kolm öösel ka juba kui ma seda koodi kirjutasin :)

(Nov 26 '09 at 19:08) Rene Saarsoo ♦♦

Siin on siis minu käkerdis :D... (enda väikesed testid pidas vastu). Mõlemad algoritmid ruumis O(1) ja kiirus O(logN).

def findMin(a):
	b = 0
	e = len(a)-1
	while e - b > 0:
		m = (b + e) / 2
		if a[b] > a[m]:
			e = m
		elif a[m] > a[e]:
			b = m+1
		else:
			return a[b]
	return a[e]

def binS(a, v, b, e):
	while b < e:
		m = ( b + e ) / 2
		mv = a[m]
		if mv < v:
			b = m + 1
		elif mv > v: 
			e = m
		else:
			return m
	if a[e] == v:
		return e
	else:
		return -1

def findVal(a, v):
	b = 0
	e = len(a)-1
	while b < e:
		m = (b + e) / 2
		mv = a[m]
		ab = a[b]
		if ab > mv:
			if (v >= mv) & (v <= a[e]):
				return binS(a, v, m, e)
			else:
				e = m
		elif mv > a[e]:
			if (v <= mv) & (v >= ab):
				return binS(a, v, b, m)
			else:
				b = m
		else:
			return binS(a, v, b, e)
	if a[e] == v:
		return e
	else:
		return -1
link

vastatud Nov 15 '09 at 21:38

egon's gravatar image

egon ♦♦
771239

edited Nov 17 '09 at 11:11

+1 mitterekursiivse lahenduse eest findMin() puhul. Selle eelis on, et kasutab mälu O(1) võrrelduna O(log2n) rekursiivsete puhul (pinu! :). findVal() saaks ju samamoodi lahendada? Kui ma ei eksi, on tegemist sabarekursiooniga (tail recursion).

(Nov 17 '09 at 07:53) Tambet Matiisen ♦♦

Tegelikult findVal on ka mitte-rekursiivne. Lihtsalt, kui meil on b ja e vaheline järjestatud, siis on kiirem kahendotsing. Muud ei olegi seal kui lülitus kahendotsinugle.

(Nov 17 '09 at 08:31) egon ♦♦

Kiire ta võib ju olla arvutile täita, aga inimesele lugeda on see kood väga-väga aeglane.

(Nov 17 '09 at 21:11) Rene Saarsoo ♦♦

Teeme siis lühidalt:

def findmax(a, start=0, rlen=0):
  test=(a[start]<=a[start+rlen/2-1]) and (a[start+rlen/2-1] < a[start+rlen/2])
  return (start+rlen-1) if rlen <= 1 else findmax(a,start+test*(rlen/2), (rlen/2)+test*(rlen % 2))


def findval(a, val, start=0, rlen=0):
  test=((a[start+rlen/2] <= v) and (v <= a[start+rlen-1])) or \
       ((a[start+rlen/2] > a[start+rlen-1]) and ((a[start+rlen/2] <= v) or (a[start+rlen-1] >= v)))
  return (start+rlen-1) if rlen <= 1 else findval(a,val,start+test*(rlen/2), (rlen/2)+test*(rlen % 2))

Või siis nüüd üldisemalt:

def bsearch(x, start, rlen, test):
  t = test(x,start,rlen)
  return (start+rlen-1) if rlen <= 1 else bsearch(x,start+t*(rlen/2), (rlen/2)+t*(rlen % 2), test)


testmax = lambda a,start,rlen: (a[start]<=a[start+rlen/2-1]) and (a[start+rlen/2-1] < a[start+rlen/2])
findmax = lambda a: bsearch(a,0,len(a),testmax)

testval = lambda (a,v),start,rlen: ((a[start+rlen/2] <= v) and (v <= a[start+rlen-1])) or \
                         ((a[start+rlen/2] > a[start+rlen-1]) and ((a[start+rlen/2] <= v) or (a[start+rlen-1] >= v)))
findval = lambda a,v: bsearch((a,v),0,len(a),testval)
link

vastatud Nov 16 '09 at 11:37

kt's gravatar image

kt ♦♦
112228

Nii et miinimumi leidmise asemel kirjutasid hoopis maksimumi leidmise funktsiooni.

(Nov 17 '09 at 21:13) Rene Saarsoo ♦♦

Nujah, kesse siis seda püstitust nii tähelepanelikult lugema viitsib. :)

(Nov 22 '09 at 20:42) kt ♦♦

Haskelli versioon:

-- Leiab v2ikseima elemendi positsiooni  
findMin :: Ord a => [a] -> Maybe Int  
findMin [] = Nothing  
findMin xs = let sorted = qsort xs  
             in scan 0 (head sorted) xs  


-- Leiab otsitava elemendi, tagastab positsiooni  
findVal :: Eq a => a -> [a] -> Maybe Int  
findVal x xs = scan 0 x xs  


{- otsib spetsifitseeritud elemendi positsiooni  
   i = positsioon e. index  
   x = otsitav element  
   (y:ys) = massiiv  
-}  
scan :: Eq a => Int -> a -> [a] -> Maybe Int  
scan _ _ [] = Nothing  
scan i x (y:ys) | x == y = Just i  
                | otherwise = scan (i+1) x ys  


-- Tavaline quicksort algoritm  
qsort :: Ord a => [a] -> [a]  
qsort (x:xs) = smaller xs ++ [x] ++ larger xs  
               where  
                  smaller xs = [a | a <- xs, a < x]  
                  larger xs = [b | b <- xs, b >= x]

Testid interpretaatoris:

*Main> findMin [5,6,7,1,2,3,4]  
Just 3  
*Main> findVal 2 [5,6,7,1,2,3,4]  
Just 4  
*Main> findVal 9 [5,6,7,1,2,3,4]  
Nothing  
*Main> findMin []  
Nothing
link

vastatud Nov 29 '09 at 16:41

Innar%20Made's gravatar image

Innar Made
112

edited Nov 29 '09 at 16:52

find_min siis minupoolt


#include <iostream>
using namespace std;


int find_min(int arr[], int len)
{
    int left_bound = 0;
    int right_bound = len - 1;
    bool b = false;

    if(len == 1 || (b=true && arr[0] > arr[1]))
    	return arr[b];

    while(true)
    {
    	int l = (right_bound + left_bound) / 2;
    	if(right_bound - left_bound <= 0 ||
                     (arr[l - 1] > arr[l] && arr[l] < arr[0]))
    		return min(arr[0], arr[l]);

    	arr[0] < arr[l] ? (left_bound = l + 1) : (right_bound = l);
    }
}

int main()
{
    int arr[] = {5,6,7,1,2,3,4};
    int ars = sizeof(arr) / sizeof arr[0];
    cout << find_min(arr, ars);
    return 0;
}
link

vastatud Dec 09 '09 at 15:09

erti%202's gravatar image

erti 2
71347

See paistab kohe mitme asja poolest kahtlane. Esiteks muutujale b omistamine tingimse sees. Kui see on kogemata ja mõeldud on võrdlust, siis on nii b ise kui ka || teine argument mõttetud. Tundib siiski, et see on meelega. Siis võiks b vähemalt täisarvuks kuulutada, aga parem selle konstruktsiooni if + else if paariga asendada ja veel parem järgneva korduse nii kirjutada, et see ka len == 1 korral õigesti töötaks. Teiseks, korduse sees võib juhtuda, et l saab väärtuseks 0 ja siis on arr[l - 1] kasutamine juba selgelt viga.

(Dec 12 '09 at 22:36) Ahto Truu ♦♦

C# variant:

class RingPuhver
{
    public static int FindMin(int[] array)
    {
        return Array.IndexOf(array, array.Min());
    }
    public static int FindVal(int[] array, int value)
    {
        return Array.IndexOf(array, value);
    }
}
link

vastatud Feb 15 '10 at 21:43

Lauri%20M.'s gravatar image

Lauri M.
11113

1

Annab muidugi õigeid vastuseid, aga suurte massiivide korral võtab nende saamine aega. Samas, kui ülesande kontekstist on ette teada, et massiivid on alati väikesed, siis tasubki just lihtsa lahenduse peale panustada.

(Feb 16 '10 at 08:40) Ahto Truu ♦♦

Kommentaar Avo lahendusele: ei oska mina midagi paremat pakkuda, aga minimaalse leidmisel võiks olla kõigepealt ka kontroll sellisele juhule, kus puhver on (juhuslikult) sorditud:

if A[R] > A[L] then
  Result := 0
link

vastatud Nov 14 '09 at 22:09

WK's gravatar image

WK
893712

Reaalsed ringpuhvrid evivad sageli lisaks pesadele ka viita puhvri "sisulisse" algusse. Viide Google suunas tähendab ilmselt, et selles ülesandes niisugust viita ei ole (muidu oleks tegemist Microsofti ülesandega), aga kuna puhvri vähima elemendi positsiooni teadaolemine ülesande sisu oluliselt mõjutab, oleks see ilus ilmutatult ära mainida.

link

vastatud Nov 17 '09 at 16:35

dig's gravatar image

dig
17415

Kui puhvri vähima elemendi indeks antud oleks, siis oleks a) küsimus ju täitsa mõttetu olnud?

(Nov 25 '09 at 13:23) Ahto Truu ♦♦

Jah, reaalses elus tuleb seda ette, et muist ülesande nüansse on tegelikult täitsa mõttetud. :-)

(Nov 27 '09 at 17:30) dig
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: Nov 14 '09 at 00:48

nähtud: 6,379 korda

viimati uuendatud: Jan 21 '11 at 19:14

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