Tìm Số Nhỏ Nhất Và Lớn Nhất Có Thể Khi Biết Số Chữ Số Và Tổng Các ...

Có thể bạn quan tâm

programmingc++ bravo16 (Cường Đỗ) October 11, 2020, 10:29am #1 Các bác cho e ý tưởng làm bài này với ạ : Cho số tự nhiên m và số nguyên s không âm, Tìm số bé nhất và lớn nhất có m chữ số và tổng chữ số bằng s, 1 ≤ m ≤ 100, 0 ≤ s ≤ 900. noname00 (HK boy) October 11, 2020, 10:30am #2 Bạn đã suy nghĩ được gì sau vài tiếng vừa rồi?https://daynhauhoc.com/t/tim-so-be-nhat-va-lon-nhat-co-m-chu-so-va-tong-chu-so-bang-s/1088396 Likes Sherly1001 (Sherly1001) October 11, 2020, 10:32am #3 Bạn đã thử nháp ra giấy chưa, làm tay sao thì làm trên máy vậy.

Số cần tìm là n = \overline{a_1a_2a_3\dots a_m} \Rightarrow a_1 + a_2 + a_3 + \dots + a_m = s.Với số nhỏ nhất:

Vì n nhỏ nhất nên tạm thời cho a_1 = 1 \Rightarrow n = \overline{1a_2a_3\dots a_m}. \Rightarrow a_2 + a_3 + \dots + a_m = s - 1

Cũng do n nhỏ nhất nên ta bắt đầu từ hàng đơn vị đi lên, gán cho a_i là giá trị lớn nhất có thể.

VD: m = 3, s = 14 \Rightarrow n = \overline{1a_2a_3} \Rightarrow n = \overline{1a_29} \Rightarrow n = \overline{149}

Với m chữ số thì s phải nhỏ hơn hoặc bằng m * 9 thì mới tìm được số thỏa mãn.

s = 0, m \ge 2 cũng không có số thỏa mãn. :v

Với số lớn nhất:

Tương tự như trên nhưng thay vì làm từ hàng đơn vị thì làm từ hàng cao nhất xuống.

VD: m = 4, s = 24 \Rightarrow n = \overline{a_1a_2a_3a_2} \Rightarrow n = \overline{9a_2a_3a_2} \Rightarrow n = \overline{99a_3a_2} \Rightarrow n = \overline{996a_2} \Rightarrow n = \overline{9960}

6 Likes HR16 (Gà Coder) October 11, 2020, 1:28pm #4 Ở phần tìm số nhỏ nhất có một vấn đề: Nếu m = 3 và s = 24 thì không thể tìm ra kết qua do số cần tìm là 699 có chữ số đầu tiên là 6 chứ không phải là 1 :V. Ở dạng tổng quát thì cách trên sẽ không sử dụng được nếu s >= 2 * m - 1 :V.5 Likes Sherly1001 (Sherly1001) October 11, 2020, 11:16am #5

chữ số đầu tiên là 6 chứ không phải là 1

Vậy nên em mới nói như v.

tạm thời cho a_1 = 1 \Rightarrow n = \overline{1a_2a_3\dots a_m}.

5 Likes tntxtnt (‏) October 11, 2020, 11:27am #6 Đảo chuỗi lớn nhất rồi thêm bớt 1 vô chữ số đầu tiên nếu cần là đc :V6 Likes HR16 (Gà Coder) October 11, 2020, 1:35pm #8 Nghĩ ra cách tìm số nhỏ nhất thoả mãn điều kiện rồi, có khả năng là sẽ chạy được hết tất cả các case hợp lệ. Cho n = \overline{a_1a_2a_3\dots a_m}, ta bắt đầu từ hàng thứ m tới hàng chục, gán cho a_i (0 < a_1 <= 9) là giá trị nhỏ nhất có thể sao cho s trừ các số còn lại (a_{i - 1}...a_1) <= 9 * (m - i), sau đó lấy s trừ tổng các chữ số ở các hàng trước là ra.Ví dụ 1: m = 3, s = 24

n = \overline{a_1a_2a_3}

n = \overline{6a_2a_3} (24 - 6 = 18, 18 = 9 * (3 - 1) = 9 * 2)

n = \overline{69a_3} (24 - 15 = 9, 9 = 9 * (2 - 1) = 9 * 1)

n = 699 (24 - 15 = 9)

Ví dụ 2: m = 2, s = 14

n = \overline{a_1a_2}

n = \overline{5a_2} (14 - 5 = 9, 9 = 9 * 1)

n = 59 (24 - 15 = 9)

Ví dụ 3: m = 3, s = 2

n = \overline{a_1a_2a_3}

n = \overline{1a_2a_3} (a_1 > 0)

n = \overline{10a_3} (2 - 0 = 2, 2 = 2 * (3 - 2) = 2 * 1)

n = 101 (2 - 1 = 1)

5 Likes Sherly1001 (Sherly1001) March 7, 2023, 7:44pm #9 Làm như v là phải tính toán nhiều hơn á. :v6 Likes Nguyen_Nhan_Tinh (bình thường) October 13, 2020, 4:56am #10 Mình viết thêm hàm tìm max:4 Likes tntxtnt (‏) October 13, 2020, 12:23pm #11 soành điệu

4 Likes Danh_Ne_Hi (Danh Nè Hí) December 28, 2021, 6:27am #12 Cái đầu tiên là phải <=0 chứ bro Nguyen_Van_Tuyen_THC (Nguyễn Văn Tuyên THCS Phú Cát - Hà Nội) December 30, 2023, 8:15am #13 số nhỏ nhất (python) Nguyen_Van_Tuyen_THC (Nguyễn Văn Tuyên THCS Phú Cát - Hà Nội) December 30, 2023, 8:14am #14 số lớn nhất (Python)