bastikk
commented
4 years ago `import random
Задача забезпечення найбільшої вигоди. -Жадібний алгоритм
На кожному кроці вибираємо найбільш вигідну дію, тим самим в кінці отримуємо найкращий,
або близький до найкращого алгоритм.
В якості прикладу будемо на кожному кроці вибирати найбільший шматок торту та з'їдати.
def eatCakes(cakePieces=[]): eatenByMe = [] while len(cakePieces) != 0: theBestPiece = max(cakePieces) eatenByMe.append(theBestPiece) # Chose the biggest piece cakePieces.remove(theBestPiece) # Remove it from cake for i in range(2): if len(cakePieces) != 0: cakePieces.remove(cakePieces[0]) # Our friends eat some piece print(eatenByMe)
eatCakes([1, 4, 7, 5, 6, 9, 8, 7, 4, 3, 2]) # Massive-the weight of cake pieces
Задача вибору розміру плитки(Розбиття участка на рівні квадратні участки). -Розділяй і володарюй.
Ми хочемо покласти плитку на підлогу у ванній кімнаті, не ріжучи плитку. Вся плитка в магазині квадратна
Треба визначити максимально можливий розмір плитки, який можна покласти у ванній кімнаті без потреби різати її
def puttingTiles(longitude, latitude): if longitude == latitude: return [longitude, latitude] # return the optimal size
Subtract from field the square parts
elif longitude > latitude:
while longitude > latitude:
longitude -= latitude
else:
while longitude < latitude:
latitude -= longitude
return puttingTiles(longitude, latitude)print(puttingTiles(1680, 640))
Задача пошуку подарунку у купі вкладених коробок(подарунок від веселих друзів).-Рекурсія.
Наші веселі друзі подарували нам коробку в якій лежать коробки, а в них іще коробки, і лише в одній них- подарунок.
Потрібно знайти даний подарунок. Для цього використаємо рекурсивний перегляд всіх коробок
def findPresent(box): for i in box: if i == 1: return i # The present is found elif len(i) == 0: pass else: return findPresent(i)
findPresent([[], [], [], [], [[], [1]]]) `
Q01.5. (*) Simulations of algorithms from everyday life • This question continues the previous one (Q01.1)
• Implement a program that simulates the implementation of certain algorithms from everyday life
•The program must show the results of both the correct execution of the algorithms and the wrong steps or the wrong sequence of steps
•This task is more difficult, but it will score more points. You can work in teams. It can be implemented in different programming languages, graphical or text interface, ...
Q01.5. (*) Моделювання алгоритмів з повсякденного життя Це питання продовжує попереднє (Q01.1)
•Реалізувати програму, що моделює виконання певних алгоритмів з повсякденного життя
•Програма має показувати результати як правильного виконання алгоритмів, так і неправильних кроків чи неправильної послідовності кроків
•Це завдання є більш складним, але за нього буде більше балів. Можна виконувати в командах. Можна реалізовувати на різних мовах програмування, графічний чи текстовий інтерфейс, …