среда, 21 апреля 2010 г.

python. Как отсортировать массив, как воспользоваться Random, ...

Сегодня на habr habr проскочила очень забавная статья:
Только 10% программистов способны написать двоичный поиск


Я бы сказал что меня зацепило. И стало интересно, а смогу ли я написать его с первого раза.

Результат ~ 45 минут и 2 прогонки.
Видно не могу я без ошибок написать такой простой алгоритм.
Попутно вынесу используемые функции в низ поста.

import random as r
import datetime as dt

def GenereytArray(elementCount, min, max):
        {
                Процедура для формирования случайного массива
                elementCount - количество элементов в массиве
                min - минимальное значение элементов
                max - максимальное значение элементов
        }
        array = [] # инициализация пустого массива
        for i in range(elementCount): # для всех элементов в диапазоне от 0 до elementCount
                r.seed(dt.datetime.now()) # передаём время для основания генератора случайных чисел
                el = r.randint(min, max) # получаем случайное число в диапазоне
                array.append(el) # добавляем элемент в массив
        array.sort() # сортировка массива
        return array # возвращаем данные

def DoBinFind(array, findelement):
        leng = len(array) # общая длина массива
        midl = int(leng//2) # середина
        delt = int(leng//2) # дельта (шаг)
        last = -1
        find = -1
        index = -1
        # пока не найден элемент или дельта не = 0
        while ((findelement != find) and (delt != 0)):
                # ищем средний элемент
                last = array[midl]
                # если элемент найден то выходим
                if last == findelement:
                        index = midl
                        break
                else:
                # иначе определяем на какой шаг нужно сдвинуться
                        delt = delt//2
                        # если средний элемент больше искомого то сдвигаемся в лево на указанный шаг
                        # иначе сдвигаемся в право
                        if last > findelement:
                                midl = midl - delt
                        else: midl = midl + delt
        # если элементы не найдены осталось проверить 1й и последний элемент
        if index == -1:
                if array[0] == findelement:
                        index = 0
                if array[leng - 1] == findelement:
                        index = leng - 1
        return index


def main ():
        # запрашиваем исходные данные
        elements = int(raw_input('elsements count -->'))
        minelement = int(raw_input('min element -->'))
        maxelement = int(raw_input('max element -->'))
        # сообщаем сколько элементов будет в массиве
        print 'genereit %s elements' % elements
        # получаем массив
        arr = GenereytArray(elements, minelement, maxelement)
        # показываем его что бы пользователь мог выбрать что ему нужно
        print arr
        # запрашиваем элемент для поиска
        f = int(raw_input('try to find digit of -->'))
        # получаем индекс искомого элемента
        ind = DoBinFind(arr, f)
        # если элемент = -1 то говорим человеческим языком
        if ind == -1:
                print 'element not found'
        else: print 'index of element is %s' % ind

main()

Итак это хороший шанс начать делать желаемое. Т.е систематизировать знания.
В текущем примере я использовал:

  • Генератор случайных чисел
    • библиотека random
    • функция random.randint(min, max)
  • Вставка данных в массив
    • [].append(element)
  • Сортировка массива
    • [].sort()
  • Динамичный запрос данных
    • raw_input('comment tekst')
  • Вывод текста на экран
    • print 'tekst %s ' % 'test'

2 комментария:

  1. Перед реализацией любого алгоритма надо сначала его понять. Я, бывает, на листочке рисую кучу списков и расчетов :)
    А вообще в двоичном поиске ничего сложного нет.
    Для развития вообще хорошо взять какую-нибудь книжку по алгоримам и "пореализовывать" их...

    ОтветитьУдалить
  2. Ну так я и не говорю что там что то сложное. я говорю что с первого раза не получилось :)

    ОтветитьУдалить