Xin đoạn code c++ về mảng

#1

Em mới học C++, gặp bài này không biết làm như thế nào kính nhờ mọi người giúp em với ạ.
Bài toán: Em có 1 mảng 1 chiều gồm n phần tử (mình nhập “n” và giá trị các phần tử ví dụ 2 3 4 5 6 7 8 9…). Và 1 số TONG ví dụ =100.
Đề ra: Cần tìm các kết quả để: a×2+b×3+c×4+d×5+…=100.
Kính mong được mọi người giúp em ạ.Em xin chân thành cảm ơn.

1 Like
#2

Ví dụ dễ hiểu hơn ạ
a[5]=[1,2,3,4,5].
b[5]=[a,b,c,d,e]
Tìm a, b, c, d, e để a×1+b×2+c×3+d×4+e×5=100

#3

Có nhiều kết quả lắm đấy.

1 Like
#4

Nghiệm nguyên à :smiley: chứ ko là tùm lum.

2 Likes
#5

giống bài thối tiền đây mà

2 Likes
#6

Vâng ạ.e muốn liệt kê hết các kết quả ạ

#7

Vâng nghiệm nguyên ạ

#9

có bài cũ đây em :V Hỏi thuật toán bài toán tìm tổng số cách đổi tiền có thể được
ko có liệt kê nghiệm :V :V chỉ có đếm có bao nhiêu nghiệm :V

4 Likes
#10

Bài này chỉ cần cho a, b, c, d, e chạy từ 0->100 rồi xét nhân vào, cái nào bằng 100 thì in ra.
Nhưng do số phần tử mảng không cố định nên có thể dùng thuật toán quay lui để liệt kê. Code mẫu thuật toán liệt kê:

#include <iostream>
#include <array>

void print(const auto& arr){
    for (const auto n: arr)
        std::cout << n << ' ';
    std::cout << '\n';
}

constexpr int MAX_VAL = 2;

void backtrack(auto& arr, size_t index){
    if (index == arr.size()){
        print(arr);
        return;
    }
    for (int i=0; i<=MAX_VAL; ++i){
        arr[index] = i;
        backtrack(arr, index+1);
    }
}

int main()
{
    std::array<int, 3> arr;

    backtrack(arr, 0);
}

Cái backtrack này cũng không dễ, nên nếu bạn không hiểu, mình gợi ý là bạn bỏ bài này không nên làm.

Sau khi liệt kê được thì chỉ còn nhân vào và so sánh nên trở thành dễ rồi.

Gợi ý tiếp cho optimize:

  1. Việc cho b, c, d, e chạy tới 100 là dư thừa, b chỉ cần chạy tới 50, bời vì 2x50==100 rồi nên b lớn hơn 50 thì chắc chắn vô nghiệm
  2. Khi a=50, thì b cũng không thể vượt quá 25, nên việc tìm có thể dừng ngay khi có kết quả hiện tại > 100, không cần tăng biến đếm nữa (hình như cái này gọi là kỹ thuật nhánh cận thì phải)
5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?