Vinnaren i pepparkakshustävlingen!
  1. Dator och IT
  2. Systemutveckling
  3. Python

Sökalgoritm python! hjälp!

Svara
2009-05-28, 13:43
  #1
Korvryttarn
Medlem
Hejhej!

Har fått i uppgift att göra en sökalgoritm i python, har kommit ungefär halvvägs men nu tar det i princip stopp, skulle kunna fråga klasspolare men då skulle de bli för lika program och läraren kanske inte skulle bevilja det.

Detta är kanske för mycket begärt, men söker då efter nån som är en glad python användare.

Postar uppgiften och så långt som jag kommit så om nån kan ge lite tips eller fortsätta på den, vad jag sett på de andra så är det inte så mycket kvar.

http://www.speedyshare.com/751273927.html = Uppgiften

http://www.speedyshare.com/541751638.html = så långt jag kommit

Verkligen tack om någon kan hjälpa lite grann, om det är så att nån kan hjälpa så gör det inte så jäkla avancerat, lätt programmering liksom. Är inte den sorts eleven som har mvg, knappt ett G

Tack
//Korvryttarn
Citera
2009-05-28, 14:09
  #2
ministaten
Medlem
ministatens avatar
Citat:
Ursprungligen postat av Korvryttarn
Hejhej!

Har fått i uppgift att göra en sökalgoritm i python, har kommit ungefär halvvägs men nu tar det i princip stopp, skulle kunna fråga klasspolare men då skulle de bli för lika program och läraren kanske inte skulle bevilja det.

Detta är kanske för mycket begärt, men söker då efter nån som är en glad python användare.

Postar uppgiften och så långt som jag kommit så om nån kan ge lite tips eller fortsätta på den, vad jag sett på de andra så är det inte så mycket kvar.

http://www.speedyshare.com/751273927.html = Uppgiften

http://www.speedyshare.com/541751638.html = så långt jag kommit

Verkligen tack om någon kan hjälpa lite grann, om det är så att nån kan hjälpa så gör det inte så jäkla avancerat, lätt programmering liksom. Är inte den sorts eleven som har mvg, knappt ett G

Tack
//Korvryttarn

programmerandet får du göra själv men algoritmen kan du få (orkar inte läsa pdf:n)

Nyckel = K

kolla elementet på halva listan, X.
- är X < K kolla på högra halvan av listan och upprepa
- är X > K kolla på vänstra halvan av listan och upprepa
- annars är K == X


Och använd CODE-taggar nästa gång istället för att länka till dina filer
Citera
2009-05-28, 14:10
  #3
Korvryttarn
Medlem
Jo jag förstår det, binary search grej typ :P
men tack ändå
Citera
2009-05-28, 14:21
  #4
Korvryttarn
Medlem
ingen som har lite fri tid?
Citera
2009-05-28, 14:31
  #5
hannes
Medlem
Kod: 
def bin_search(list, num, tries = 0):
    i = len(list)/2
    if list[i] == num: return("det tog dig %s forsok" %tries)
    elif list[i] < num: return bin_search(list[i+1:], num, tries + 1)
    elif list[i] > num: return bin_search(list[:i], num, tries + 1)

randlist.sort()
print bin_search(randlist, Valt_nummer)

Detta kanske funkar...
Citera
2009-05-28, 15:33
  #6
Korvryttarn
Medlem
Okej, jo det kanske de gör, ska testea lite, tänkte iaf klistra in koden här nu så ni kan kolla o hjälpa lite om ni vill och kan!
All hjälp jag få uppskattas!

Kod: 
i
mport random

def random_num(number1,number2,number3):
    '''skapar osorterad lista'''
    return [random.randint(1, 19) for tal in range(0,20)]

def sok_dum (list, number):
    '''soker igenom listan'''
    number_of_tries = 0
    for number in range(0,len(list)):
        number_of_tries += 1
        if list[number] == Valt_nummer:
            return("det tog dig %s forsok" %number_of_tries)

def hitta_mitten(lower, upper)
    middle = (upper - lower) / 2
    middle = middle + lower
    return middle
    

randlist = random_num(1,19,20)
Valt_nummer = randlist[random.randint(0,len(randlist) - 1)]
    

print(sok_dum(randlist,Valt_nummer))

def sok_smart(list, number):
    '''soker igenom sorterad lista'''
    index = 0
    upper_bound = len(list) - 1
    lower_bound = 0
    while hitta_mitten()
        hitta_miten()
        if random_num[hitta_mitten] > Valt_nummer:
        
        elif random_num[hitta_mitten] < Valt_nummer:
    
        else:

Hoppas det blev lite lättare nu iaf, har kommit lite längre än när jag skapade tråden!

Tack
Korvryttarn
Citera
2009-05-28, 16:29
  #7
Korvryttarn
Medlem
ingen?
Citera
2009-05-30, 15:16
  #8
SSH
Medlem
SSHs avatar
Här är en iterativ variant som bara använder en jämförelse i loopen. Personligen tycker jag att de rekursiva varianter är vackrare. Speciellt om man bara är intresserad av antalet jämförelser. I en rekursiv variant behöver man då ingen variabel som håller reda på antalet varv. Istället kan man använda return binarySearch(i, j) + 1.

Kod:
import random

def random_num(number1,number2,number3):
    '''skapar osorterad lista'''
    return [random.randint(1, 19) for tal in range(0,20)]

def hitta_mitten(lower, upper):
    middle = (upper - lower) / 2
    middle = middle + lower
    return middle

def sok_dum (list, number):
    '''soker igenom listan'''
    for i in range(0,len(list)):
        if list[i] == number:
            return "det tog dig %s forsok" % (i + 1)

def sok_smart(list, number):
    '''soker igenom sorterad lista'''
    low = 0
    high = len(list)
    number_of_tries = 0
    while low < high: 
        number_of_tries += 1
        mitten = hitta_mitten(low, high)
        if number > list[mitten]:
            low = mitten + 1
        else:
            high = mitten
    if low < len(list) and list[low] == number:
        return "det tog dig %s forsok" % number_of_tries

randlist = random_num(1,19,20)
randlist.sort()
valt_nummer = randlist[random.randint(0,len(randlist) - 1)]

print(sok_dum(randlist, valt_nummer))
print(sok_smart(randlist, valt_nummer)) 
Citera
Svara

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback