Zielwertsuche in einem sortierten Array

5 Lösungen

#303

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ß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von AlexGroeg (2010 Punkte) - 30.12.2020 um 19:12 Uhr

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) )