0
import random
import time
import math

#среднее значение
def average_value(numbers):
    return float(sum(numbers) / max(len(numbers)))

class node:
    def __init__(self, value = None):
        self.value = value
        self.left_child= None
        self.right_child= None
        self.parent= None # указатель на род. узел в дереве

class binary_search_tree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root == None:
            self.root = node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = node(value)
                cur_node.left_child.parent = cur_node # установаливаем род
            else:
                self._insert(value, cur_node.left_child)
        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = node(value)
                cur_node.right_child.parent = cur_node # установаливаем род
            else:
                self._insert(value,cur_node.right_child)
                # если уже есть данный эл, то не добавляем
    
    def search(self, value):
        if self.root != None:
            return self._search(value, self.root)
        else:
            return True

    def _search(self, value, cur_node):
        if value == cur_node.value:
            return True
        elif value < cur_node.value and cur_node.left_child != None:
            return self._search(value, cur_node.left_child)
        elif value > cur_node.value and cur_node.right_child != None:
            return self._search(value, cur_node.right_child)
        return False

tree = binary_search_tree()

succ = []
fail = []

i = 0

#заполнение дерева
for i in range(10000):
    tree.insert(int(random.random() * 10 ** 4))
    i += 1
    print(i)

#поиск в дереве
for i in range(10 ** 3):
    rand = int(random.random() * 10 ** 4)
    start_time = time.time()
    result = tree.search(rand)
    finish_time = time.time() - start_time
    if result == True:
        succ.append(finish_time)
    else:
        fail.append(finish_time)

if (len(succ) == 0):
    print("Нет успешных результатов поиска!")
else:
    min_time = min(succ)
    max_time = max(succ)
    average_time = average_value(succ)

    sum = 0

    for i in range(len(succ)):
        sum += (succ[i] - average_time) ** 2

    deviation_time = math.sqrt((1 / i) * sum) # стандартное отклонение

    print("")
    print("")

    print("min time: " + str(min_time))
    print("max time: " + str(max_time))
    print("average time: " + str(average_time))
    print("deviation time: " + str(deviation_time))

print("")
print("")

if (len(fail) == 0):
    print("Нет неудачных результатов поиска!")
else:
    average_time = average_value(fail)

    sum = 0

    for i in range(len(fail)):
        sum += (fail[i] - average_time) ** 2

    deviation_time =  math.sqrt((1 / i) * sum) # стандартное отклонение

    print("average time: " + str(average_time))
    print("deviation time: " + str(deviation_time))

1 ответ 1

2
def _insert(self, value, cur_node):
    if value  cur_node.value:

Что за хитрый if?

def _search(self, value, cur_node):
    if value == cur_node.value:
        return True
    elif value  cur_node.value and cur_node.right_child != None:

Аналогично

Ну и конкретно по вашему вопросу:

def average_value(numbers):
    return float(sum(numbers) / max(len(numbers)))

вы передаёте в функцию вот такой список

[0.0, 0.0, 0.0, 0.0, 0.0]

угадайте что происходит :)

надо сделать так:

def average_value(numbers):
    return float(sum(numbers) / len(numbers))

Тогда у вас ошибка уже вот тут:

deviation_time = math.sqrt((1 / i) * sum)  # стандартное отклонение

Деление на 0

Так что надо проверять еще и i, например так:

deviation_time = 0 if i == 0 else math.sqrt((1 / i) * sum)  # стандартное отклонение

тогда код уже не выдает ошибок и доходит до конца

1
  • ошибка была в sum(numbers). Я считал, что sum(numbers) - это метод. Оказывается нет.
    – user405273
    7 дек 2020 в 5:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.