Ду ишоракунак

Ду ишоракунак — усулест, ки дар он ду индекс якбора аз массив ҳаракат мекунанд. Он бисёр ҳалҳои «ҳамаи ҷуфтҳоро гузаштан»-ро аз n² қадам ба n қадам табдил медиҳад.

Ишоракунакҳо ба сӯи ҳамдигар

Масъала: дар рӯйхати мураттаб ду ададро бо суммаи x ёфтан. Гузаштани ҳамаи ҷуфтҳо — n² санҷиш. Вале оқилонатар кардан мумкин аст:

a = [1, 3, 4, 6, 8, 11]
x = 10
i, j = 0, len(a) - 1
while i < j:
    s = a[i] + a[j]
    if s == x:
        print(a[i], a[j])   # 4 6
        break
    elif s < x:
        i += 1    # сумма хурд аст — адади чапи калонтар мегирем
    else:
        j -= 1    # сумма калон аст — адади рости хурдтар мегирем

Чаро ин дуруст аст: агар a[i] + a[j] аз x хурд бошад, a[i] бо ягон элементи аз j чаптар мувофиқ намеояд (ҳамаашон боз хурдтаранд) — онро партофтан мумкин аст. Барои канори рост низ ҳамин тавр. Ҳар қадам як элементро мепартояд, бинобар ин қадамҳо на бештар аз n-тоанд.

Ишоракунакҳо ба як самт: якҷояшавӣ

Ду ишоракунак метавонанд аз ду рӯйхати гуногун гузаранд. Масалан, барои ёфтани элементҳои умумии ду рӯйхати мураттаб:

a = [1, 2, 4, 5, 7]
b = [2, 3, 5, 7, 9]
i = j = 0
common = []
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        common.append(a[i]); i += 1; j += 1
    elif a[i] < b[j]:
        i += 1
    else:
        j += 1
print(common)    # [2, 5, 7]

Ҳамеша ишоракунакеро ҳаракат медиҳем, ки ба адади хурдтар нигоҳ мекунад: он дигар бо ҳеҷ чизи минбаъдаи рӯйхати дигар мувофиқ омада наметавонад.

Нуқтавергул ; имкон медиҳад, ки якчанд фармонро дар як сатр нависем — ин мумкин аст, вале суиистифода кардан лозим нест.

Тирезаи дарозиаш тағйирёбанда

Истифодаи маъмултарин — тирезаи лағжанда: порчаи [left, right], ки сарҳади росташ як элементӣ ба пеш меравад, чапаш бошад вақте ки тиреза «бад» шуд, ба он мерасад.

Мисол: дарозии порчаи дарозтарине, ки дар он ҳамаи ададҳо ҷуфтанд:

a = [2, 4, 1, 6, 8, 10, 3, 2]
left = 0
best = 0
for right in range(len(a)):
    if a[right] % 2 == 1:     # тиреза бо адади тоқ бад аст —
        left = right + 1      # тирезаи навро пас аз он сар мекунем
    best = max(best, right - left + 1)
print(best)    # 3  (6, 8, 10)

Нақшаи умумии тиреза:

left = 0
for right in range(n):
    # 1. a[right]-ро ба тиреза илова кардан
    # 2. то даме ки тиреза бад аст — a[left]-ро гирифта, left-ро ҳаракат додан
    # 3. тирезаи [left, right] хуб аст — ҷавобро нав кардан

Барои кор кардани нақша чунин хосият лозим аст: агар тиреза хуб бошад, ҳар тирезаи дохили он ҳам хуб аст. Он гоҳ сарҳади чап ҳеҷ гоҳ ба қафо баргаштан лозим намешавад.

Нигоҳ доштани «дар тиреза чӣ ҳаст»-ро тағйирёбандаҳо (сумма, ҳисобкунак) ё луғат (ҳар элемент дар тиреза чанд бор вомехӯрад) кумак мекунанд.

Ин чӣ қадар арзиш дорад

Гарчанде ки дар дохили for метавонад while бошад, ишоракунаки left дар тамоми барнома на бештар аз n бор ҳаракат мекунад. Бинобар ин ҳамагӣ тақрибан 2n қадам мешавад, на n².

Хулоса

• ишоракунакҳо ба сӯи ҳамдигар — ҷустуҷӯи ҷуфт дар массиви мураттаб;
• ишоракунакҳо аз рӯи ду рӯйхат — якҷояшавӣ, буриш;
• тирезаи лағжанда: right ба пеш меравад, left вақте ки тиреза бад шуд, мерасад;
• ҳар ишоракунак массивро як бор мегузарад — тақрибан n қадам ҳосил мешавад.