1-ээс n хүртэлх тооноос k-г сонгох бүх аргыг backtracking ашиглан өсөх дарааллаар нь гаргадаг арга.

IntermediateХугацаа: O(C(n, k) · k)Санах ой: O(k)

Эхлээд жижиг бодлого

1-ээс 4 хүртэлх тооноос 2-ыг сонгох бүх аргыг бичье. Тоог үргэлж өсөх дарааллаар авбал:

1 2, 1 3, 1 4, 2 3, 2 4, 3 4. Нийт 6 сонголт. Томьёогоор C(4, 2) = 4 · 3 / 2 = 6.

Энгийн аргаас санаа руу

Энгийн арга: k давхар loop бичнэ. Гэтэл k нь оролтоос ирдэг бол хэдэн давхар loop бичихээ мэдэхгүй.

Гол санаа: recursion. solve(i, x) нь c[i] байранд x-ээс эхлэн тоо тавиад, дараагийн байрыг solve(i + 1, v + 1)-ээр бөглөнө. k байр бүгд бөглөгдөхөд хэвлэнэ. Дараагийн тоо үргэлж өмнөхөөсөө их тул {1, 2} ба {2, 1} хоёр тусдаа гарахгүй.

Нэр томьёо ба тэмдэглэгээ

solve(i, x)
c[0..i - 1] бөглөгдсөн. c[i] байранд x буюу түүнээс их тоо тавина.
c[]
Одоогийн сонголт. Хэвлэх үед c[0] < c[1] < … < c[k - 1].
base case
i == k: бүх байр бөглөгдсөн, сонголтоо хэвлээд буцна.
n - (k - i) + 1
c[i] байранд тавьж болох хамгийн их тоо. Үүнээс их бол үлдсэн байранд тоо хүрэхгүй.
C(n, k)
n-ээс k-г сонгох аргын тоо: n! / (k! · (n - k)!).
{}
n = 5k = 3
Call stack
solve(0, 1)

1-ээс 5 хүртэлх тооноос 3 ширхгийг сонгох бүх аргыг олъё. Дараалал чухал биш: {1,2} ба {2,1} нэг л сонголт. Тиймээс тоог үргэлж өсөх дарааллаар авна.

Алхам 1 / 30
Хурд
  • Одоогийн дуудлага
  • Хүлээж буй дуудлага
  • Дууссан
  • Олдсон сонголт
Слайд 1 / 6

Баг сонгоно

5 найзаасаа 3-ыг тэмцээнд явуулна. Хэдэн янзаар сонгох вэ? Дараалал чухал биш тул тоог үргэлж өсөх дарааллаар авна. Ингэвэл нэг багийг хоёр удаа тоолохгүй.

k-combinations.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, c[20];
void solve(int i, int x) {
if (i == k) {
for (int j = 0; j < k; j++) cout << c[j] << ' ';
cout << '\n';
return;
}
for (int v = x; v <= n - (k - i) + 1; v++) {
c[i] = v;
solve(i + 1, v + 1);
}
}
int main() {
cin >> n >> k;
solve(0, 1);
return 0;
}

Юунд хэрэгтэй вэ?

Бүх сонголтыг нэг бүрчлэн үзэх шаардлагатай бодлогод (баг бүрдүүлэх, хослол шалгах) хэрэглэнэ. Тоог өсөх дарааллаар авдаг тул нэг сонголт хоёр удаа гарахгүй.

Яаж ажилладаг вэ?

1. solve(i, x): c[0..i − 1] сонгогдсон, дараагийн тоо x буюу түүнээс их. 2. i = k бол сонголт бэлэн, хэвлэнэ. 3. Үгүй бол v = x, x + 1, … тоог c[i] байранд тавиад solve(i + 1, v + 1) гэж дуудна. 4. v ≤ n − (k − i) + 1 байна. Үүнээс их тоо авбал үлдсэн байранд тоо хүрэхгүй. Оролт: n ба k. Гаралт: сонголт бүр нэг мөрөнд.

Яагаад зөв, хэр хурдан бэ?

Өсөх дараалалтай k тоо бүрийг код яг нэг удаа гаргана. Эхний тоо нь c[0]-ийн loop-д нэг л удаа тавигдаж, дараагийнх нь дотор recursion-д нэг л удаа тавигдана. Өсөх дараалалтай тул нэг олонлог хоёр өөр дарааллаар гарахгүй.

Дээд хязгаар n - (k - i) + 1 нь мухар салааг таслах тул recursion-ы мод дахь салаа бүр хариутай. Хугацаа O(C(n, k) · k). n = 20, k = 10 бол 184 756 сонголт, хормын төдий.

Түгээмэл алдаа

  • Recursion-д v + 1 биш i + 1 дамжуулах. Тэгвэл дараагийн тоо өмнөхөөсөө бага байж болох тул нэг сонголт хэд хэд гарна.
  • Дээд хязгаарыг зүгээр n гэж бичих. Хариу зөв ч хэвээр, гэхдээ мухар салаанд илүү цаг үрнэ.
  • Хэвлэх үед c дотор k-р байрнаас хойш үлдсэн хуучин утгыг хэвлэх. Зөвхөн c[0..k - 1].
  • C(n, k) маш хурдан өсдөг. n = 30, k = 15 бол 155 сая сонголт тул бүгдийг хэвлэх боломжгүй.

Хязгаарын тохиолдол

  • k = n: ганц сонголт, 1 2 … n.
  • k = 1: n сонголт, тоо бүр нэг мөрөнд.
  • n = 1, k = 1: 1 хэвлэнэ.

Өөрийгөө шалга

  1. 1-ээс 4 хүртэлх тооноос 3-ыг сонгох хэдэн арга бий вэ?

    Хариу харах

    4: 1 2 3, 1 2 4, 1 3 4, 2 3 4.

  2. n = 5, k = 3 үед c[0] хамгийн ихдээ хэд байж болох вэ?

    Хариу харах

    3. 5 - (3 - 0) + 1 = 3. Тэгвэл 3 4 5 гарна.

  3. C(6, 3) хэд вэ?

    Хариу харах

    20.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 5, k = 2 үед хэвлэгдэх бүх мөрийг бич.

    Hint харах

    1-ээр эхэлсэн 4, 2-оор эхэлсэн 3 гэх мэт.

    Хариу ба тайлбар

    1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5. Нийт 10.

  2. 2.Хэвлэхгүйгээр зөвхөн нийлбэр нь S-тэй тэнцүү сонголтын тоог тоол.

    Hint харах

    solve-д одоогийн нийлбэрийг нэмэлт параметр болгож дамжуул.

    Хариу ба тайлбар

    solve(i, x, sum). i == k үед if (sum == S) cnt++. n = 5, k = 3, S = 9 бол 1 3 5, 2 3 4 гэсэн 2 сонголт.

  3. 3.Array-н элементүүдээс k-г сонгох бүх аргыг гарга. Тоо биш, a array-н элементүүдийг хэвлэ.

    Hint харах

    Index-ийг сонгож, хэвлэхдээ a[c[j]] гэж бич.

    Хариу ба тайлбар

    Index-ийг 0-ээс n - 1 хүртэл сонгоно: loop v = x; v <= n - (k - i); v++, эхлэх нь solve(0, 0). Хэвлэхдээ a[c[j]].

Жишээ

Оролт

4 2

Гаралт

1 2
1 3
1 4
2 3
2 4
3 4