[Thuật toán] Tính bình phương của 1 số gồm n số 1

Tháng Chín 24, 2013 nguyenvanquan7826 Thuật toán Leave a response

Đề bài:

Cho số S = 111…11 (n chữ số 1, hệ thập phân), tính S^2.
Input
– Dòng đầu tiên: số lượng test k (k<=40).
– k dòng tiếp, mỗi dòng ghi số n – số lượng chữ số 1 của S. (1 <= n <= 1000000)
Output
– Với mỗi test ghi kết quả trên 1 dòng.
Example
Input:
2
1
2
Output:
1
121

Cách giải:
Ta thấy KQ có dạng đối xứng 123…n…321. VD n=3 thì 111^2 = 12321
Nhưng nhận thấy với n =10 thì dạng đối xứng này có vẻ không đúng lắm.
VD: với n = 13 tức là ta có 1111111111111^2.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
            1111111111111
           1111111111111
          1111111111111
         1111111111111
+       1111111111111
       1111111111111
      1111111111111
     1111111111111
    1111111111111
   1111111111111
  1111111111111
 1111111111111
1111111111111
=========================
1234567901234320987654321

Chúng ta thấy quy luật đối xứng không còn nữa. Và mình nảy ra một ý định đó là thế này. Ta cứ viết như đối xứng đi, rồi thực hiện như sau:

Ta sẽ thực hiện in từng số từ phải sang trái và ta có code sau:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
using namespace std;
int main()
{
        int k, n;
 
        cin>>k;
        for (int i=0; i<k; i++)
        {
            cin>>n;
            string s = "";
            int temp = 0;   // temp la phan du khi chi so cho 10. VD 13 thi temp la 1.
            int j = 1, ji = 1;
            // bat dau viet tu phai sang trai
            while (j>0)
            {
                // cong tung cap nhu hinh ((j+temp)%10)
                //sau do chen vao giua
                s.insert(0, 1, (char)((j+temp)%10+'0'));
                temp = (j+temp)/10;
                if (j==n) ji = -1;  // quay nguoc lai khi du n so
                j += ji;
            }
        cout<<s<<endl;
        }
    return 0;
}

Sau khi có code trên, xuất một số KQ thì rút ra quy luật như sau:
Dãy số chia làm 3 phần phần đầu có cấu trúc như sau :
+/ phần đầu: 123456790123456790123456790… tức là lặp lại của đoạn 123456790 (n-1)/9 = n1 lần.
+ phần giữa: 123…x…32 với x = n – 9*n1.
+/ phần cuối: lặp n1 lần 098765432 và có số 1 ở cuối cùng. Để đơn giản ta cứ cho phần giữa là đối xứng tức là có dạng 12321 rồi ta chèn phần cuối vào trước số 1 ở cuối.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int k, n;
     
    cin>>k;
    for (int i=0; i<k; i++)
    {
        cin>>n;
        string s = "", s1 = "123456790", s2 = "098765432";
        int n1 = (n-1)/9, n2 = n - 9*n1;
         
        // doan giua
        for (int i=1; i<=n2; i++)
            s.insert(s.length(), 1, (char)(i + '0'));
             
        for (int i=n2-1; i>0; i--)
            s.insert(s.length(), 1, (char)(i + '0'));
         
        // neu n tu 10 tro len
        if (n>9)
        {
            // doan dau
            for (int i=0; i<n1; i++)
                s.insert(0, s1);
            // doan cuoi
            for (int i=0; i<n1; i++)
                s.insert(s.length()-1, s2);
        }
        cout<<s<<endl;
    }
    return 0;
}

Minh họa KQ khi nhập k =13 và 5 số n (14, 37, 30, 113, 352) tuơng ứng như trong hình.