Sumowanie elementów list - Python

Załóżmy, że dane są dwie listy A i B liczb naturalnych, posortowane rosnąco oraz dana liczba naturalna x. Napisać program, który sprawdza, czy istnieją takie a z listy A i b z listy b, że x=a+b. Rozwiązanie ,,brzydkie" (a w zasadzie nieoptymalne), czyli metodą ,,brute force" (o złożoności kwadratowej) jest za 2 punkty, rozwiązanie ciekawsze (o lepszym rzędzie złożoności) za 4 punkty.

Pomoże ktoś? Poniższy program który napisałam mi niestety nie działa.

print('Podaj x:')
x = input()

def sumujdox(A,B):
  n=len(A)
  a=A[0]
  m=len(B)
  b=B[0]

  for i in range(n):
    a=A[i]

    for j in range(m):
      b=B[j]
      if x == a+b:
         print ('a=',a,'b=',b)

      else:
          j=j+1

    if x == a+b:
      print ('a=',a,'b=',b)

    else:
      i=i+1

L1=[0,1,2,3,9]
L2=[0,1,3,4,6]  

print(sumujdox(L1,L2))

Przekombinowałeś, ale próbowałeś więc masz działające wersje

x = 9

def czteryp(taba, tabb):
    def szukbin(liczba, tab):
        lewo = 0
        prawo = len(tab) - 1
        while lewo < prawo:
            srod = int((lewo + prawo ) / 2)
            if tab[srod] < liczba:
                lewo = srod + 1
            else:
                prawo = srod
        if tab[prawo] == liczba:
            return prawo
        return -1
    for liczba in taba:
        tymcz = szukbin(x - liczba, tabb)
        if tymcz != -1:
            return ("szukan to", liczba, tabb[tymcz])
    return("brak")

def dwap(taba, tabb):
    for liczba in taba:
         if x - liczba in tabb:
            return ("szukan to", liczba, x - liczba)
    return("brak")


L1=[0,1,2,3,9]
L2=[0,1,3,4,6]  
print(czteryp(L1,L2))
print(dwap(L1,L2))

edit: zapomniałem wspomnieć że wersję za 4 punkty da się jeszcze trochę przyśpieszyć, zastanów się jak.

Dziękuję, ale problem jest taki, że kompletnie nie rozumiem co się dzieje w tym programie po kolei. Nie dało by się jakoś poprawić tego, co napisałam? Jesteśmy na poziomie początkującym.

Tylko, że program przestaje działać, jak jedna lista jest dłuższa od drugiej. To na pewno nie miało być coś takiego, bo to po prostu jest jeszcze dla nas za trudne - przed tym zadaniem mieliśmy wyszukiwanie elementu maksymalnego w liście.

Masz tak jak chyba próbowałaś zrobić, ale moje rozwiązanie jest bardziej "pythonowe":

x = 11

def dwap(taba, tabb):
    for i in range(len(taba)):
        for j in range(len(tabb)):
            if taba[i] + tabb[j] == x:
                return (taba[i], tabb[j])
    return("brak")


L1=[0,1,2,3,9]
L2=[0,1,3,4,6]  
print(dwap(L1,L2))

O, to jest zdecydowanie to co miałam na myśli. Pytanie tylko co zrobić, żeby program nie kończył po znalezieniu pierwszej pary, bo np. jeśli w L2 dopiszę 2 i dam x=5, to powinno mi dać (1,4) oraz (2,3)

w takim razie najłatwiej będzie zrobić listę z wynikami, ograniczałem się do pierwszego żeby było szybciej.

x = 9



def dwap(taba, tabb):
    wynik = []
    for i in range(len(taba)):
        for j in range(len(tabb)):
            if taba[i] + tabb[j] == x:
                 wynik.append([taba[i], tabb[j]])
    if len(wynik) == 0:
        return ("brak")
    return wynik


L1=[0,1,2,3,9]
L2=[0,1,3,4,6]  
print(dwap(L1,L2))

Zadanie domowe: stringi w Pythonie i jak umieszczać w nich wyniki obliczeń, bo nauczyciel / wykladowca / itp pewnie sobie tego zażyczy.

Super :) Bardzo dziękuję

Hm, chyba nie ma sensu parsować wszystkich elementów, które spełniają x > a i x > b, skoro mamy mieć sumę x = a + b.

from bisect import bisect_left
from itertools import product

x = 35
L1 = [2, 7, 14, 25, 25, 28, 32, 39, 42, 49]
L2 = [1, 2, 5, 7, 15, 18, 21, 29, 38, 45, 47, 50]

L1 = L1[:bisect_left(L1, x)]
L2 = L2[:bisect_left(L2, x)]
result = [i for i in product(L1, L2) if sum(i) == x]  # [(14, 21), (28, 7)]

Edit: product zamiast combinations.