สมมติว่าเรามีตัวเลขสองตัว n และ k เราต้องเลือกจำนวนสูงสุดขององค์ประกอบที่แตกต่างกันจาก 1 ถึง n โดยที่ไม่มีสับเซต (subset) ใดที่ผลรวมเท่ากับ k หากพบ ให้คืนค่าตัวเลขที่เลือก
เช่น ถ้าค่าที่ป้อนเข้าเป็น n = 5; k = 3 ผลลัพธ์จะได้ [4, 5, 2]
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
สำหรับ i := (k + 1) / 2 เมื่อ i <= k - 1 เพิ่ม i ทีละ 1 ทำ: พิมพ์ i สำหรับ i := k + 1 เมื่อ i <= n เพิ่ม i ทีละ 1 ทำ: พิมพ์ i
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; void solve(int n, int k) { for (int i = (k + 1) / 2; i <= k - 1; i++) { cout << i << ", "; } for (int i = k + 1; i <= n; i++) { cout << i << ", "; } } int main() { int n = 5; int k = 3; solve(n, k); }
ข้อมูลนำเข้า
5, 3
ข้อมูลส่งออก
2, 4, 5,
