Python :: Aufgabe #303
5 Lösungen
Zielwertsuche in einem sortierten Array
Fortgeschrittener - Python
von JKooP
- 21.11.2020 um 09:10 Uhr
Aufgabe 1 (leicht)
In einem beliebig großen sortieren Array soll das erste Vorkommen desjenigen Zahlenpaares per Index ausgegeben werden, bei dem die Summe dem gesuchten Zielwert entspricht.
Dabei kommt jede Zahl nur einmal im Array vor.
arr = [3, 4, 15, 22]
target = 7
Index = [0, 1] (3+4)
arr = [1, 3, 4, 6]
target = 8
Index = [0, 0] oder NULL/Nothing (keine Lösung)
Aufgabe 2 (mittel)
Wie Aufgabe 1, jedoch können Zahlen doppelt vorkommen.
arr = [4, 4, 5, 6]
target = 8
Index = [0, 1] (4+4)
Aufagbe 3 (schwer)
In einem beliebig großen sortieren Array sollen alle Vorkommen derjenigen Zahlenpaare per Indizes ausgegeben werden, bei denen die Summen dem gesuchten Zielwert entsprechen. Dabei können alle Zahlen mehrfach vorkommen.
arr = [1, 3, 4, 6]
target = 7
Indizes = [0, 3] (1+6), [1, 2] (3+4)
Noch ein wenig schwieriger:
arr = [4, 4, 4, 5, 6]
target = 8
Indizes = [0, 1] (4+4), [0, 2] (4 + 4), [1, 2] (4 + 4)
Für alle Aufgaben gilt:
Dopplungen wie [1, 3] und [3, 1] gelten als gleichwertig und sollen nicht ausgegeben werden.
Viel Spaß
In einem beliebig großen sortieren Array soll das erste Vorkommen desjenigen Zahlenpaares per Index ausgegeben werden, bei dem die Summe dem gesuchten Zielwert entspricht.
Dabei kommt jede Zahl nur einmal im Array vor.
arr = [3, 4, 15, 22]
target = 7
Index = [0, 1] (3+4)
arr = [1, 3, 4, 6]
target = 8
Index = [0, 0] oder NULL/Nothing (keine Lösung)
Aufgabe 2 (mittel)
Wie Aufgabe 1, jedoch können Zahlen doppelt vorkommen.
arr = [4, 4, 5, 6]
target = 8
Index = [0, 1] (4+4)
Aufagbe 3 (schwer)
In einem beliebig großen sortieren Array sollen alle Vorkommen derjenigen Zahlenpaare per Indizes ausgegeben werden, bei denen die Summen dem gesuchten Zielwert entsprechen. Dabei können alle Zahlen mehrfach vorkommen.
arr = [1, 3, 4, 6]
target = 7
Indizes = [0, 3] (1+6), [1, 2] (3+4)
Noch ein wenig schwieriger:
arr = [4, 4, 4, 5, 6]
target = 8
Indizes = [0, 1] (4+4), [0, 2] (4 + 4), [1, 2] (4 + 4)
Für alle Aufgaben gilt:
Dopplungen wie [1, 3] und [3, 1] gelten als gleichwertig und sollen nicht ausgegeben werden.
Viel Spaß
Lösungen:
Python-Code
test_data = [ ([3, 4, 15, 22], 7), ([1, 3, 4, 6], 8), ([4, 4, 5, 6], 8), ([1, 3, 4, 6], 7), ([4, 4, 4, 5, 6], 8) ] def search_target(array, target): solution = [] for index1 in range(len(array)): for index2 in range(index1 + 1, len(array)): if array[index1] + array[index2] == target: solution.append((index1, index2)) print(f'arr = {array}') print(f'target = {target}') if solution: print(f'Index = {solution}\n') else: print(f'No Solution\n') for array, target in test_data: search_target(array, target)
Python-Code
def get_index(arr, target): index = [] for i in range(0, len(arr) - 1): for j in range(i + 1, len(arr)): if arr[i] + arr[j] == target: index.append([i, j]) # folgende Kommentierung für die leichten Beispiele entfernen '''break''' else: continue if arr[i] + arr[j] > target: break # folgende Kommentierung für die leichten Beispiele entfernen '''if index: break''' if not index: index = [[0, 0]] return index input_arr = [4, 4, 4, 5, 6] input_tar = 8 print(get_index(input_arr, input_tar))
Python-Code
# 303 Zielwertsuche in einem sortierten Array # -------------------------------- arr = [3, 4, 15, 22] target = 7 #Index = [0, 1] (3+4) arr1 = [1, 3, 4, 6] target1 = 8 Index = [] def Aufgabe1(list, target): n = 2 for i in list: if i <= target: if n > 0: target -= i Index.append(list.index(i)) n -= 1 if target == 0: return Index if target > 0: Index.clear() return Index print( 'Index =', Aufgabe1(arr, target)) print( 'Index =', Aufgabe1(arr1, target1)) # -------------------------------- arr3 = [4, 4, 5, 6] target3 = 8 Index = [] #Index = [0, 1] (4+4) def Aufgabe2(liste,target): n = 2 for e in range(len(liste)-1): if liste[e] <= target: if n > 0: target -= liste[e] Index.append(e) n -= 1 if target == 0: return Index if target > 0: Index.clear() return print( 'Index =', Aufgabe2(arr3, target3)) # ------------------------------------- import itertools arr4 = [1, 3, 4, 6] target4 = 7 Index = [] #Indizes = [0, 3] (1+6), [1, 2] (3+4) def rotate(r): r.append(r.pop(0)) return(r) def Aufgabe3(liste,target): for i in itertools.permutations(liste,2): if sum(i) == target: l=[] for e in i: l.append(liste.index(e)) Index.append(l) # doppelte entfernen Indizes = [] for i in Index: if i not in Indizes and rotate(i) not in Indizes: Indizes.append(rotate(i)) return(Indizes) print('Indizes =', Aufgabe3(arr4, target4) )
Python-Code
arr = [1, 3, 4, 6] target = 7 a = 0 while a < len(arr): for i in range(a+1 ,len(arr)-a): sum =(arr[a] +arr[i]) if sum == target: print("[ "+ str(a)+ " , "+str(i)+"]") a +=1
Python-Code
def search(data, tar): k = range(len(data)) res = [tuple(ij) for ij in {frozenset((i, j)) for i in k for j in k if i != j and data[i] + data[j] == tar}] res.sort() if res: return {ij: f"{data[ij[0]]} + {data[ij[1]]} = {tar}" for ij in res} else: return "Keine Lösung" # Test: testdata = [([3, 4, 15, 22], 7), ([1, 3, 4, 6], 8), ([4, 4, 5, 6], 8), ([1, 3, 4, 6], 7), ([4, 4, 4, 5, 6], 8)] for row in testdata: print(search(row[0], row[1]))