algorithm correctly solves a given problem. Correct algorithms usually come with
a proof of correctness, which is an explanation of why we know that the algorithm
must take every instance of the problem to the desired result
a proof of correctness, which is an explanation of why we know that the algorithm
must take every instance of the problem to the desired result
The following pseudocode presents a simplified version of the tabu search algorithm as described above. This implementation has a rudimentary short-term memory, but contains no intermediate or long-term memory structures. The term "fitness" refers to an evaluation of the candidate solution, as embodied in an objective function for mathematical optimization.
pseudocode of tabu search :
pseudocode of tabu search :
sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
sNeighborhood ← getNeighbors(bestCandidate)
bestCandidateFitness ← -∞
for (sCandidate in sNeighborhood)
if ( (not tabuList.contains(sCandidate))
and (fitness(sCandidate) > bestCandidateFitness) )
bestCandidate ← sCandidate
bestCandidateFitness ← fitness(bestCandidate)
end
end
if (bestCandidateFitness is -∞)
break;
end
if (bestCandidateFitness > fitness(sBest))
sBest ← bestCandidate
end
tabuList.push(bestCandidate)
if (tabuList.size > maxTabuSize)
tabuList.removeFirst()
end
end
return sBest
# runtime > O(log) : logarithmic time
def binary_search(list, item):
low = 0
high = len(list) -1
step = 0
while low <= high:
step = step + 1
mid = (low + high)
guess = list[mid]
if guess == item:
print("number of steps :" , step)
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
# runtime > O(n) : linear time
def linear_search(list , item):
step = 0
for x in list :
step = step + 1
if x == item :
print("number of steps : ", step)
return item
return None
mylist = [1 , 3 , 5 , 12 , 15 , 21, 22 , 23 , 24 ,25 ]
print ("len array : " , mylist.__len__())
# Selection sorts
# operation runtime O(n2) because it takes 2 operations + a O(1) : constant time for looping and making the task done.
def find_smallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selection_sort(arr):
newArr = []
for i in range(len(arr)):
smallest = find_smallest(arr)
newArr.append(arr.pop(smallest))
return newArr
###
import random
newlist = sorted(mylist, key=lambda x: random.random())
print("new list :" , newlist)
newlist = selection_sort(newlist)
print("sorted list using selection sort :" , newlist)
# O(log n) is faster than O(n), but it gets a lot faster as the list of items
# you’re searching grows.
print(binary_search(mylist , 22))
print(linear_search(mylist , 25))
Divide and Conquer is a problem-solving strategy that involves breaking down a complex problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. It is a widely used algorithmic technique in computer science and mathematics.
من چقدر باید این ریکرژنو ایتریشنو سورتینگ پترن رو بخونم تا توی کلم بره
A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".
image_2024-02-25_17-53-02.png
356 KB
وقتی که حتی روی یه فانکشن ساده هم دیباگر میزنی تا بفهمی داره توی call stack چه غلطی میکنه
recursive binary search implementation :
note:
_ with every recall using return with their function will cause re-run the function with their provided (args)
_ in the recall method the state of the variables must have to be passed because of reruring the function proccess
def binary_search_recv(list, number , low , high):
if low > high:
return -1
mid = (low + high)
guess = list[mid]
if guess == number:
return mid
if guess > number:
return binary_search_recv(list , number , low , mid - 1)
else:
return binary_search_recv(list, number , mid + 1 , high)
note:
_ with every recall using return with their function will cause re-run the function with their provided (args)
_ in the recall method the state of the variables must have to be passed because of reruring the function proccess
Factory Implementation
from abc import ABC, abstractmethod
class FormatNotFound(Exception):
pass
class File(ABC):
def __init__(self, file):
self.file = file
@abstractmethod
def make(self):
pass
def call_edit(self):
product = self.make()
result = product.edit(self.file)
return result
class JsonFile(File):
def make(self):
return Json()
class XmlFile(File):
def make(self):
return Xml()
class Json:
def edit(self, file):
return f'working on {file}.json'
class Xml:
def edit(self, file):
return f'working on {file}.xml'
def client(file, format):
try:
formats = {
'json': JsonFile
, 'xml': XmlFile
}
result = formats[format](file)
return result.call_edit()
except KeyError:
raise FormatNotFound
if __name__ == '__main__':
print(client('test', 'json'))