Chủ đề này có 8 trả lời

[Dinh Ha]

Đề bài là thế này:
Cho số nguyên dương n, người ta viết các số nguyên liên tiếp từ 1 tới n trong hệ thập phân để tạo ra 1 dãy các chữ số. Tính tổng các chữ số của dãy.

Input
Một số n duy nhất (n <= 10^100)

Output
Số nguyên duy nhất là kết quả tìm được

ví dụ:
n=3 thì output là 6
n=20 thì output là 102
tính theo kiểu: 1+2+3+4+5+6+7+8+9+1+0+1+1+1+2+1+3+1+4+1+5+1+6+1+7+ 1+8+1+9+2+0= 102

Do bài này giới hạn n rất lớn(100 chữ số) nên phải tìm đc quy luật để tính tổng từ số n.
Mình thử tìm quy luật của nó mà ko ra.
Ai pit thì giúp mình với

Bài viết đã được chỉnh sửa nội dung bởi Dinh Ha: 03-05-2011 - 15:01

[perfectstrong]

Đề bài là thế này:
Cho số nguyên dương n, người ta viết các số nguyên liên tiếp từ 1 tới n trong hệ thập phân để tạo ra 1 dãy các chữ số. Tính tổng các chữ số của dãy.

Input
Một số n duy nhất (n <= 10^100)

Output
Số nguyên duy nhất là kết quả tìm được

ví dụ:
n=3 thì output là 6
n=20 thì output là 102
tính theo kiểu: 1+2+3+4+5+6+7+8+9+1+0+1+1+1+2+1+3+1+4+1+5+1+6+1+7+ 1+8+1+9+2+0= 102

Do bài này giới hạn n rất lớn(100 chữ số) nên phải tìm đc quy luật để tính tổng từ số n.
Mình thử tìm quy luật của nó mà ko ra.
Ai pit thì giúp mình với

Bài này không có quy luật gì cả. Chỉ đơn giản là cho số nhập vào là 1 chuỗi n.
Cho i chạy từ 1 đến n với i là kiểu chuỗi.
Ứng dụng chương trình cộng 2 số có 200 chữ số vào là ra.

[Dinh Ha]

Mình vẫn chưa hiểu ý bạn. Nếu cho i chạy từ 1 tới n thì với n<=10^100 thì sao mà chạy nỗi

[perfectstrong]

Mình vẫn chưa hiểu ý bạn. Nếu cho i chạy từ 1 tới n thì với n<=10^100 thì sao mà chạy nỗi

Bạn tạo ra 1 hàm là incs(i) mang dữ liệu là kiểu chuỗi; trong đó, i là biến kiểu chuỗi.
Hàm này cho ra số tiếp theo của i.
Ví dụ: incs('1234567891234567891234567891321323291')='1234567891234567891234567891321323292'
incs('1234567891234567891234567891321323291234567854213215469')='1234567891234567891234567891321323291234567854213215470'
Với hàm này thì dùng trong pascal là chạy được.
Đề cho n tối đa là 100 chữ số thì ta dùng kiểu string vì kiểu string có độ dài tối đa (trong turbo pascal) là 255 (trong free pascal thì đến 2 tỷ kí tự).

Hay nói tóm lại, ta xử lí bài toán bằng kiểu dữ liệu string.

[BadMan]

Bạn tạo ra 1 hàm là incs(i) mang dữ liệu là kiểu chuỗi; trong đó, i là biến kiểu chuỗi.
Hàm này cho ra số tiếp theo của i.
Ví dụ: incs('1234567891234567891234567891321323291')='1234567891234567891234567891321323292'
incs('1234567891234567891234567891321323291234567854213215469')='1234567891234567891234567891321323291234567854213215470'
Với hàm này thì dùng trong pascal là chạy được.
Đề cho n tối đa là 100 chữ số thì ta dùng kiểu string vì kiểu string có độ dài tối đa (trong turbo pascal) là 255 (trong free pascal thì đến 2 tỷ kí tự).

Hay nói tóm lại, ta xử lí bài toán bằng kiểu dữ liệu string.

Cách của perfectstrong đúng rồi đấy nhưng ở đây n không phải có 100 chữ số mà là 10^100 (số chữ số lớn hơn nhiều). Vấn đề nêu ra tiếp cận ở góc độ TIN HỌC (không phải TOÁN HỌC nhé) thì cách giải quyết sẽ là:

- Độ phức tạp về không gian: Khả năng lưu trữ là hữu hạn (không có khái niệm ở trong Toán học)
- Độ phức tạp về thời gian: Khả năng tính toán (thời gian thực hiện để cho ra kết quả) dựa trên số phép toán cầnthuwch hiện.

Quya trở lại với bài toán của bạn. Trong trường hợp kiểu chuỗi bị tràn (số có số chữ số vượt 255) thì dùng dách sách liên kết đơn (ứng dụng kiểu con trỏ) khi đó chiều dài số là vô biên theo nghĩa còn đủ bộ nhớ để tạo ra các biến động.

Tóm lại, cũng là một vấn đề nhưng tiếp cận theo góc độ Toán học và Tin học thì cách giải quyết có thể khác nhau (nhưng vẫn giải quyết được cùng yêu cầu).

[starr]

Cách của perfectstrong đúng rồi đấy nhưng ở đây n không phải có 100 chữ số mà là 10^100 (số chữ số lớn hơn nhiều). Vấn đề nêu ra tiếp cận ở góc độ TIN HỌC (không phải TOÁN HỌC nhé) thì cách giải quyết sẽ là:

- Độ phức tạp về không gian: Khả năng lưu trữ là hữu hạn (không có khái niệm ở trong Toán học)
- Độ phức tạp về thời gian: Khả năng tính toán (thời gian thực hiện để cho ra kết quả) dựa trên số phép toán cầnthuwch hiện.

Quya trở lại với bài toán của bạn. Trong trường hợp kiểu chuỗi bị tràn (số có số chữ số vượt 255) thì dùng dách sách liên kết đơn (ứng dụng kiểu con trỏ) khi đó chiều dài số là vô biên theo nghĩa còn đủ bộ nhớ để tạo ra các biến động.

Tóm lại, cũng là một vấn đề nhưng tiếp cận theo góc độ Toán học và Tin học thì cách giải quyết có thể khác nhau (nhưng vẫn giải quyết được cùng yêu cầu).

Bài này có 2 vấn đề:
- Số n cho giới hạn là <= 10^100 thì tối đa nó có 100 chữ số là đúng rồi vì số 10^100 có 100 chữ số thôi.
- Nếu làm theo kiểu perfectstrong thì liệu máy tính có chạy nỗi ko, với vòng lặp 10^100 lần và với tốc độ của máy tính hiện khoảng >3GHz không biết đến khi nào nó mới chạy xong vòng lặp đó=> Cách này không khả thi cho lắm
Mình nghĩ nếu bài này tìm ra quy luật tính hay công thức tính thì nó sẽ giảm độ phức tạp của thuật toán rất nhiều.
Ai tìm đc quy luật hay công thức thì share lên để mọi người cùng tham khảo

[hxthanh]

Moi bài này lên! Nào ai là người đưa ra được công thức $S_n$ với $n$ là số nguyên dương bất kỳ?

[nmlinh16]

Ký hiệu $s(k)$ là tổng các chữ số của một số tự nhiên $k$ và $$S_n = \sum_{k < n} s(k).$$ Ta cần tính $S_n + s(n)$.
Ta có thể tính $S_n$ bằng đệ quy với công thức $$\begin{cases} S_0 = 0 \\ S_n = 10S_m + 45m + r \cdot s(m) + \frac{r(r-1)}{2}\end{cases}$$ với $m = \left\lfloor\frac{n}{10}\right\rfloor$ và $r = n-10m$.
Thật vậy, theo định nghĩa trên thì $m$ và $r$ lần lượt là phần chục và chữ số hàng đơn vị của $n$. Mỗi số tự nhiên $k < n$ có dạng $k = 10m' + r'$ với $m' < m$ và $r' \in \{0,1,\ldots,9\}$ hoặc $k = 10m + r'$ với $r' \in \{0,1,\ldots,r-1\}$. Do đó $$\begin{align*} S_n & = \sum_{m' < m} \sum_{r' = 0}^9 s(10m' + r') + \sum_{r'=0}^{r-1}s(10m+r) \\ & = \sum_{m' < m} \sum_{r' = 0}^9 (s(m') + r') + \sum_{r'=0}^{r-1} (s(m)+r') \\ & = \sum_{m' < m} (10s(m') + 45) + r \cdot s(m) + \frac{r(r-1)}{2} \\ & = 10 S_m + 45m + r \cdot s(m) + \frac{r(r-1)}{2}.\end{align*}$$
Để xác định độ phức tạp về thời gian $T(n)$ khi tính theo công thức truy hồi trên, nhận xét rằng $$T(n) = T\left(\frac{n}{10}\right) + O(\log n),$$ nên theo định lý Master thì $T(n) = O(\log^2 n)$, tức là bằng hàm đa thức bậc hai theo cỡ của input. Từ công thức truy hồi trên có thể tính ra $S_n + s(n)$ theo các chữ số của $n$, nhưng mình chưa đủ kiên nhẫn để thử.

Bài viết đã được chỉnh sửa nội dung bởi nmlinh16: 15-07-2023 - 08:53

[poset]

Bổ đề

 $\sum_{i=10^km}^{10^k(m+1)-1}s(k)=10^ks(m)+45\cdot 10^{k-1}k$.

Chứng minh

Các số từ $10^km$ đến $10^k(m+1)-1$ có dạng $\overline{ma_1a_2...a_k}, 0\leq a_i\leq 9$. Số hạng đầu tiên từ việc chuỗi $m$ ở đầu xuất hiện $10^k$ lần. Số hạng thứ hai từ việc với $0\leq i\leq 9$, $i$ xuất hiện $10^{k-1}k$ lần trong tất cả chuỗi $k$ số $\overline{a_1a_2...a_k}, 0\leq a_i\leq 9$ ($10^{k-1}$ lần mỗi vị trí $a_j$, có $k$ vị trí như vậy) và $45=0+1+2+...+9$.

Giả sử $n=\overline{a_1a_2...a_m}$. Theo Theorem, ta có: $$\begin{align*} S_n & =\sum_{i=1}^{n}s(i)=\sum_{k=1}^{m}\sum_{i=10^{m-k}\cdot \overline{a_1...a_{k-1}0}}^{10^{m-k}\cdot \overline{a_1...a_{k-1}a_k}-1}s(i) \\ & =\sum_{k=1}^{m}\sum_{i=0}^{a_k-1}\sum_{j=10^{m-k}\cdot\overline{a_1...a_{k-1}i}}^{10^{m-k}\cdot(\overline{a_1...a_{k-1}i}+1)-1}s(j) \\ & =\sum_{k=1}^{m}\sum_{i=0}^{a_k-1}(10^{m-k}(\sum_{j=1}^{k-1}a_j+i)+45\cdot 10^{m-k-1}(m-k)) \\ & =\sum_{k=1}^{m}(a_k(10^{m-k}\sum_{j=1}^{k-1}a_j+45\cdot 10^{m-k-1}(m-k))+10^{m-k}\sum_{i=0}^{a_k-1}i) \\ & =\sum_{1\leq k<l\leq m}10^{m-l}a_ka_l+\sum_{k=1}^{m}(45\cdot 10^{m-k-1}(m-k)a_k+10^{m-k}\frac{a_k(a_k-1)}{2}) \end{align*}$$.

Bài viết đã được chỉnh sửa nội dung bởi poset: 15-07-2023 - 12:48