Cần giúp đỡ bài tập tìm một số nguyên dương không quá n có tổng các chữ số lớn nhất

Son_Huynh · October 6, 2019, 3:49pm

Nhập một số nguyên dương n.
Tìm một số nguyên dương <= n sao cho tổng của các chữ số trong số nguyên dương đó là lớn nhất

rogp10 · October 5, 2019, 6:19am

Nhồi số 9 nhiều vào là win chặt luôn

Son_Huynh · October 5, 2019, 11:05am

cái này dạng như tính tổng từng số một nó chạy vòng lặp nhiều quá không biết làm sao h

rogp10 · October 6, 2019, 11:24am

Khi n không có dạng (k+1)*10^d - 1, ta thấy rằng k*10^d - 1 là đáp án với tổng số chữ số là 9(d-1) + k-1 = 9d + k - 10. Giả sử tồn tại một số nhỏ hơn n nhưng có tổng chữ số là 9d + k - 9 = 9(d-1) + k. Mà chữ số thập phân không thể quá 9 và k cũng vậy, suy ra mâu thuẫn.

DoTran1 · October 7, 2019, 11:38am

Tôi k biết C++, tôi đang code = java.
Mong mn cùng thảo luận

public class MainClass {
	public static void main(String[] args) {
		timSo(8899);
	}
	private static int loga(int n) {
		int i = 0;
		while (n > 0) {
			n=n/10;
			i++;
		}
		return i;
	}
	private static int timSo(int n) {
		int soChuSo = loga(n);
		int heso = (int)Math.pow(10, soChuSo-1);
		int ketQua =0;
		while (soChuSo > 1) {
			soChuSo--;
			ketQua += 9*(int)Math.pow(10, soChuSo -1);
		}
		ketQua = ((n/heso) * heso + ketQua <= n) ? ((n/heso) * heso + ketQua) : ((n/heso - 1) * heso + ketQua);
		System.out.println("So lon nhat la: " + ketQua);
		return ketQua; //7999
	}
}

Son_Huynh · October 31, 2019, 2:38am

Dù em mới học không biết java nhưng em cũng cảm ơn bác vì giúp em nhé

Để nghiên cứu phát

tntxtnt · October 8, 2019, 2:27am

ketqua “sơ bộ” 99…9 lấy heso - 1 là ra rồi mà

3 dòng :

int tens = 1;
while (tens <= n) tens *= 10;
return (n + 1) % (tens /= 10) ? n - n % tens - 1 : n;

DoTran1 · October 8, 2019, 2:07am

mn cùng thảo luận về thuật toán thôi, chứ ngôn ngữ nào cũng giống nhau mà, chỉ khác syntax.
Tôi cũng chưa biết cách của mình đã phải tối ưu chưa.
Ý tưởng:
Tìm n là số có bao nhiêu chữ số.
VS: n = 8899 => có 4 chữ số
KQ = a999.
Ở đây a = 8 (chữ số đầu tiên của n) hoặc a = 7 (số đầu tiên của n - 1). So sánh KQ với 2 trường hợp của a với n.
Cách làm này có vẻ k tốt về hiệu năng. mn cùng thảo luận nhé

rogp10 · October 8, 2019, 2:24am

n - n % tens - 1 : n thôi

tntxtnt · October 8, 2019, 2:26am

ko có nút likeee mạnh

DoTran1 · October 8, 2019, 2:38am

Tôi thấy chưa ổn.
while (tens <= n) tens *= 10
phải thêm tens /= 10;

return (n + 1) % (tens /= 10) ? n - n % tens - 1 : n;
điều kiện trước dấu ? chưa phải là 1 biểu thức boolean.

DoTran1 · October 8, 2019, 2:40am

Trong trường hợp ngta yêu cầu KQ phải là số lớn nhất thì làm như thế nào các bạn.
VD: n = 989 // KQ phải trả về là 989 chứ k phải 899
Ai có ý tưởng gì k nhỉ?

tntxtnt · October 8, 2019, 3:00am

đúng rồi, có “ăn gian” chia 10 ở dòng return đó C++ nó lỏng lẻo ở chỗ cho phép chuyển int thành bool, int có giá trị khác 0 là true, 0 là false, nếu Java thì thêm > 0 thành (n + 1) % (tens /= 10) > 0 ? ... hay != 0 cũng đc, C++ thì ko cần thiết

số lớn nhất thì tính digitSum(n) có bằng digitSum(…999) thì trả về n là xong :V :V

ý ko đc, có trường hợp
n=797 cachedBrute=789 fast=699
:V :V

n=998 cachedBrute=998 fast=899
n=997 cachedBrute=989 fast=899
n=996 cachedBrute=989 fast=899
n=995 cachedBrute=989 fast=899
n=994 cachedBrute=989 fast=899
n=993 cachedBrute=989 fast=899
n=992 cachedBrute=989 fast=899
n=991 cachedBrute=989 fast=899
n=990 cachedBrute=989 fast=899
n=989 cachedBrute=989 fast=899
n=898 cachedBrute=898 fast=799
n=897 cachedBrute=889 fast=799
n=896 cachedBrute=889 fast=799
n=895 cachedBrute=889 fast=799
n=894 cachedBrute=889 fast=799
n=893 cachedBrute=889 fast=799
n=892 cachedBrute=889 fast=799
n=891 cachedBrute=889 fast=799
n=890 cachedBrute=889 fast=799
n=889 cachedBrute=889 fast=799
n=798 cachedBrute=798 fast=699
n=797 cachedBrute=789 fast=699
n=796 cachedBrute=789 fast=699
n=795 cachedBrute=789 fast=699
n=794 cachedBrute=789 fast=699
n=793 cachedBrute=789 fast=699
n=792 cachedBrute=789 fast=699
n=791 cachedBrute=789 fast=699
n=790 cachedBrute=789 fast=699
n=789 cachedBrute=789 fast=699
n=698 cachedBrute=698 fast=599
n=697 cachedBrute=689 fast=599
n=696 cachedBrute=689 fast=599
n=695 cachedBrute=689 fast=599
n=694 cachedBrute=689 fast=599
n=693 cachedBrute=689 fast=599
n=692 cachedBrute=689 fast=599
n=691 cachedBrute=689 fast=599
n=690 cachedBrute=689 fast=599
n=689 cachedBrute=689 fast=599
n=598 cachedBrute=598 fast=499
n=597 cachedBrute=589 fast=499
n=596 cachedBrute=589 fast=499
n=595 cachedBrute=589 fast=499
n=594 cachedBrute=589 fast=499
n=593 cachedBrute=589 fast=499
n=592 cachedBrute=589 fast=499
n=591 cachedBrute=589 fast=499
n=590 cachedBrute=589 fast=499
n=589 cachedBrute=589 fast=499
n=498 cachedBrute=498 fast=399
n=497 cachedBrute=489 fast=399
n=496 cachedBrute=489 fast=399
n=495 cachedBrute=489 fast=399
n=494 cachedBrute=489 fast=399
n=493 cachedBrute=489 fast=399
n=492 cachedBrute=489 fast=399
n=491 cachedBrute=489 fast=399
n=490 cachedBrute=489 fast=399
n=489 cachedBrute=489 fast=399
n=398 cachedBrute=398 fast=299
n=397 cachedBrute=389 fast=299
n=396 cachedBrute=389 fast=299
n=395 cachedBrute=389 fast=299
n=394 cachedBrute=389 fast=299
n=393 cachedBrute=389 fast=299
n=392 cachedBrute=389 fast=299
n=391 cachedBrute=389 fast=299
n=390 cachedBrute=389 fast=299
n=389 cachedBrute=389 fast=299
n=298 cachedBrute=298 fast=199
n=297 cachedBrute=289 fast=199
n=296 cachedBrute=289 fast=199
n=295 cachedBrute=289 fast=199
n=294 cachedBrute=289 fast=199
n=293 cachedBrute=289 fast=199
n=292 cachedBrute=289 fast=199
n=291 cachedBrute=289 fast=199
n=290 cachedBrute=289 fast=199
n=289 cachedBrute=289 fast=199
n=198 cachedBrute=198 fast=99
n=197 cachedBrute=189 fast=99
n=196 cachedBrute=189 fast=99
n=195 cachedBrute=189 fast=99
n=194 cachedBrute=189 fast=99
n=193 cachedBrute=189 fast=99
n=192 cachedBrute=189 fast=99
n=191 cachedBrute=189 fast=99
n=190 cachedBrute=189 fast=99
n=189 cachedBrute=189 fast=99
n=98 cachedBrute=98 fast=89
n=88 cachedBrute=88 fast=79
n=78 cachedBrute=78 fast=69
n=68 cachedBrute=68 fast=59
n=58 cachedBrute=58 fast=49
n=48 cachedBrute=48 fast=39
n=38 cachedBrute=38 fast=29
n=28 cachedBrute=28 fast=19
n=18 cachedBrute=18 fast=9

dường như là nó + 1 vào hàng cao nhất, chuyển bớt số 1 từ hàng nào cho <= n là được

DoTran1 · October 8, 2019, 3:02am

VD tens = 1000
Vậy là tens/10 ở trước ? là 100, vậy sau dấu ? tens = 100 hay 1000 vậy bạn?
return của bạn mình đã sửa thành
((n+1) / tens * tens - 1) <= n ? (n+1) / tens * tens - 1 : n;

tntxtnt · October 8, 2019, 3:06am

sau dấu ? tens = 100

ở trước đó: tens /= 10 là gán tens = tens / 10, rồi tính giá trị (n+1)% tens

(n + 1) % (tens /= 10) ?
có nghĩa là
tính a = n + 1 và b = tens /= 10 cùng lúc (ko theo thứ tự trái phải hay phải trái)
tính c = a % b
xét c != 0

DoTran1 · October 8, 2019, 3:06am

à, tôi k để ý có dấu “=”
thanks

tntxtnt · October 8, 2019, 3:07am

ăn gian 1 dòng tens /= 10 đó mà

tntxtnt · October 14, 2019, 1:53pm

int fast(int n) { // n > 0
    int tens = 1;
    while (tens <= n) tens *= 10;
    int ret = (n + 1) % (tens /= 10) ? n - n % tens - 1 : n;
    int ret2 = ret + tens;
    for (int t = 1; t < tens; t *= 10)
        if (ret2 - t <= n)
            return ret2 - t;
    return ret;
}

số lớn nhất <= n có tổng các chữ số lớn nhất :V

cộng tens lại thành a999…99, rồi trừ t = 1, 10, 100, …, được kết quả <= n thì return giá trị mới, còn ko thì return giá trị cũ (a-1)999…99 :V

test drive n=1 tới 100 triệu: https://rextester.com/AOQOD93360

code xogn rồi nghĩ ra cách chứng minh cũng dễ:
(a-1)999…99 là số có tổng chữ số lớn nhất mà <= n, và cũng là số lớn nhất mà < a000…00
với các số > a000…00, số có tổng các chữ số bằng (a-1)999…99 sẽ có dạng chữ số a đầu tiên, 1 chữ số 8, còn lại toàn chữ số 9. Vậy từ (a-1)999…99 ta chuyển thành a999…99 rồi trừ từ từ t=1,10,100,… tới khi nào ra số <= n là được, nếu ko có thì ko có số > a000…00 mà có tổng các chữ số lớn nhất, trả về (a-1)999…99

có thể rút gọn thành 5 dòng :V

int fast(int n) { // n > 0
    int tens = 1;
    while (tens <= n) tens *= 10;
    int ret = (n + 1) % (tens /= 10) ? n - n % tens - 1 + tens : n + tens;
    for (int t = 1; t <= tens; t *= 10)
        if (ret - t <= n) return ret - t;
    // return 0; //never reach, kệ bà compiler nó hú
}

+ tens ở trong ? : để tránh undefined behavior :V