Một số kỹ thuật sử lý "số cực lớn" bằng xâu trong c++ mà có thể bạn chưa biết
đã đăng vào 27, Tháng 6, 2022, 9:23Một số kỹ thuật sử lý "số cực lớn" bằng xâu trong c++ mà có thể bạn chưa biết
lưu ý:
- dưới đây là những code đã được mình chọn lọc, kiếm duyệt nên bạn có thể tin tưởng 90% 🤣🤣.
- dù được chọn lọc nhưng: một số code dưới đây có thể chạy chậm, hoặc có thể chưa tối ưu. Do đó, bạn hãy cân nhắc khi sử dụng, và nếu có code tối ưu hơn hãy gửi lại qua facebook cá nhân của mình: Phung Hieu 😘
- các thuật toán dưới đây đều dựa trên cách tính cộng, trừ, nhân. chia hồi tiểu học 🤣🤣.
- các giá trị số dưới đây đều là xâu nha. 🤣🤣
#. Cộng số lớn:
string csl(string a, string b)
{
int du = 0;
int mid = 0;
string res = "";
a.insert(0, max(0, (int) (b.length() - a.length())), '0');
b.insert(0, max(0, (int) (a.length() - b.length())), '0');
for (int i = a.length()-1; i >= 0; --i)
{
mid = ((int) a[i] - 48) + ((int) b[i] - 48) + du;
du = mid / 10;
res = (char) (mid % 10 + 48) + res;
}
if (du > 0) res = "1" + res;
return res;
}
Cách gọi hàm này: csl(a, b);
#. Trừ số lớn:
lưu ý: số trừ phải lớn hơn số bị trừ (a > b). Nếu bạn không đáp ứng điều kiện này thì máy tính của bạn sẽ như lúc bạn hồi học tiểu học gặp được phép tính 1 - 2 vậy. 🤣🤣🤣
string tsl(string a, string b)
{
int du = 0;
int mid = 0;
string res = "";
a.insert(0, max(0, (int) (b.length() - a.length())), '0');
b.insert(0, max(0, (int) (a.length() - b.length())), '0');
for (int i = a.length()-1; i >= 0; --i)
{
mid = ((int) a[i] - 38) - ((int) b[i] - 48) - du;
du = (mid < 10) ? 1 : 0;
res = (char) (mid % 10 + 48) + res;
}
while (res[0] == '0' && res.length() > 1) res.erase(0, 1);
return res;
}
Cách gọi hàm này: tsl(a, b);
#. Nhân số lớn
lưu ý:
- hàm này sẽ bao gồm 2 hàm nhỏ.
- nhân số bé (nhân 1 số [1..9] với 1 xâu).
- nhân số lớn.
- hàm này có kết hợp với hàm cộng số lớn (csl).
string nsb(string a, int b, int l)
{
string res = "";
int mid = 0;
int du = 0;
for (int i = a.length() - 1; i >= 0; --i)
{
mid = ((int) a[i] - 48) * b + du;
du = mid / 10;
res = (char) (mid % 10 + 48) + res;
}
if (du > 0)
{
string k = to_string(du);
res = k + res;
}
res.insert(res.length(), l, '0');
return res;
}
string nsl(string a, string b)
{
string res = "";
for (int i = b.length() - 1; i >= 0; --i)
{
string t = nsb(a, (int) b[i] - 48, b.length() - i - 1);
res = csl(res, t);
}
return res;
}
Cách gọi hàm này: nsl(a, b);
#. Cuối cùng là: Chia số lớn.
lưu ý:
- hàm này kết hợp với 2 hàm khác:
- hàm so sánh 2 số (cmp).
- hàm trừ số lớn (tsl).
- hàm này (nếu bạn hiểu ra) thì nó là hàm dài nhất
Đầu tiên là hàm so sánh 2 số "dạng xâu":
int cmp(string a, string b)
{
a.insert(0, max(0, (int)(b.length() - a.length())), '0');
b.insert(0, max(0, (int)(a.length() - b.length())), '0');
if (a > b) return 1;
if (a == b) return 2;
return 3;
}
hàm chia:
string chsl(string a, string b, string t)
{
string tb[11];
tb[0] = "0";
for (int i = 1; i <= 10; ++i) tb[i] = csl(tb[i-1], b);
string hold = a.substr(0, b.length()-1);
cout << hold << endl;
string res = "";
for (int i = b.length()-1; i <= (int) a.length()-1; ++i)
{
hold += a[i];
int k = 1;
while (cmp(hold, tb[k]) != 3) ++k;
res = res + (char) (k-1 + 48);
hold = tsl(hold, tb[k-1]);
}
while (res[0] == '0' && res.length() > 1) res.erase(0, 1);
if (t == "div") return res;
else return hold;
}
Cách gọi hàm này:
- Chia lấy phần nguyên: chsl(a, b, "div");
- Chia láy dư: chsl(a, b, "mod"); hoặc thay "mod" bằng một giá trị bất kì nào đó đều được, ví dụ: "i love you".