Cách xử lý số lớn

#1

Em viết chương trình chạy với các số lớn nhưng chương trình toàn báo lỗi dù đã chọn kiểu số lớn. Cho e hỏi với vấn đề này thì mình cần xử lý như thế nào?
Theo code của e thì e cần nhập mảng có số phẩn tử lớn và giá trị các phần tử của mảng cũng rất lớn.

#include<iostream>
using namespace std;

int main(){
	unsigned long n,A[1000000],d=1,t;
	cin>>n;
	for(unsigned long i=1;i<=n;i++){
		cin>>A[i];
		if(i==1){t=A[i];
		}
		if(i!=1){
			if(t>A[i]) {
                                   t--
                                 };
		else {
			t=A[i];
			d++;
		       }
		  }
	}
	cout<<d;
}
1 Like
#2

hình như mảng A của bạn hơi bị to

#3

Số của bạn lớn cỡ bao nhiêu?
Bạn bị lỗi gì?

p/s: Bạn format lại code đi cho mọi người dễ nhìn thì mới giúp bạn nhanh được :slight_smile:

#4

chương trình của bạn đang làm gì vậy

#5

Đây là đề bài mình đang làm, viết bằng tiếng Anh nên bạn chịu khó nhé:slight_smile:

There are N balloons floating in the air in a large room, lined up from left to right. Young Perica likes to play with arrows and practice his hunting abilities. He shoots an arrow from the left to the right side of the room from an arbitrary height he chooses. The arrow moves from left to right, at a chosen height H until it finds a balloon. The moment when an arrow touches a balloon, the balloon pops and disappears and the arrow continues its way from left to right at a height decreased by 1. Therefore, if the arrow was moving at height H, after popping the balloon it travels on height H-1. Our hero’s goal is to pop all the balloons using as little arrows as possible.

#6

Đúng rồi bạn, chình vì to quá nên mình muốn hỏi các bạn xử lý bài toán khi số liệu nhập vào lớn :frowning:

#7

Đề yêu cầu giá trị <1 000 000 bạn ạ
Chương trình mình vừa chạy là báo lỗi, yêu cầu đóng lại luôn. :frowning:

#8

mảng bạn khai báo tầm 10000 phần tử thôi. 1 tỷ nó báo lỗi là đúng

#9

Vậy nếu đề yêu cầu số liệu là 10^6 thì mình xử lý làm sao vậy bạn?

#10

ý bạn là bạn cần xử lý 1 triệu số 1 lúc à. hay xử lý một vài số to thôi

#11

bạn hiểu con số 1 triệu này ntn

#12

Mình hiểu mảng này có 1 tỷ phần tử

#13

Mình nhớ có một kiểu số là BigInt 128 bit.
Nhưng nếu một mảng lơn như vậy chưa chắc hệ điều hành có thể cấp phát 1 dảy các bit liên tiếp được.
Dùng DSLK thì quá trình duyệt sẽ rất chậm.

Với lại cái đề mình đọc xong thấy còn mơ hồ lắm,không hiểu ý nó là sao,
các quả bóng được quản lý bằng mảng (<=1000000), với giá trị từng phần tử là chiều cao của quả bóng ứng với vị trí đó.
nếu vậy thì dùng dslk được (vì ko cần truy xuất ngẫu nhiên)

Pasted image706×41 2.13 KB

Mủi tên sẽ là việc bắt đầu với quả bóng có cùng chiều cao đầu tiên, sau đó giảm 1, tíếp tục duyệt từ trái sang phải từ vị trí i+1 để tìm quả có cùng chiều cao kế tiếp rồi như vậy đến phần tử cuối cùng.
. Quả bóng nổ là giá trị ==0.

hay dùng mảng 2 chiều để quản lý các quả bóng?

Cái này dùng dslk cũng đc. nhưng mỗi phần tử sẽ liên kết với phần từ phía sau và phía dưới nó. phần từ cuối hàng liên kết với phần từ đầu hàng tiếp theo.
nếu vậy thì cần 1 mảng cờ hiệu để làm dấu hàng bong bóng ở độ cao (hàng i) đã bị bắn hết chưa.

có lẽ phải dùng thuật toán vét cạn.

có phải vậy không bạn. .

1 Like
#14

Mình nghĩ là sai chỗ bạn khai báo mảng A có 10^6 phần tử. Đề cho 1 <= n <= 10^6. Bạn cho i chạy từ 1 --> nếu n = 10^6 thì bạn sẽ access A[10^6] tức phần tử thứ 10^6 + 1 …

p/s: với điều kiện đề bài cho thì bạn chỉ cần dùng int là được rồi :slight_smile:

#15

Mình cũng k biết chắc nữa. Đề bài chỉ cho có vậy :frowning:

#16

int là khoảng [－ 32768 … 32767], giả sử có giá trị i= 1 000 000 thì vượt quá phạm vi kiểu int rồi bạn :slight_smile:
Vậy theo bạn tại sao khi vừa chạy chương trình mà đã báo lỗi luôn, k dk nhập bất kì kí tự nào vào?

#17

int của c++ có đến 32 bit lận mà, ko vượt quá được đâu

#18

Khai báo mảng lớn thì nên khai báo ngoài tất cả chương trình con. Bài này có liên quan gì đến số lớn đâu?
Thuật toán bài này mình nghĩ chỉ cần tham lam là dc. Mỗi lần bắn tất nhiên sẽ bắn ở đầu mảng và ở vị trí H lớn nhất. Giả sử lúc quả bóng đang ở vị trí i và độ cao H thì quả bóng tiếp theo ở vị trí (j,H’) phải thoã mãn dk (j>i) && (H’< H) và j gần i nhất. Dùng piority_queue sẽ cho phép xác định cặp (j,H’) này trong logn. Cứ mỗi lần duyệt đến cuối mảng, nếu mảng chưa hết thì duyệt lại từ đầu mảng với những phần tử còn lại. Dpt(nlogn)

#19

không nghĩ là 1 triệu phần tử. Dạng bignum thường thì nhập bằng chuỗi rồi chuyển qua số lưu trên mảng. Trên mạng có nhiều hướng dẫn về bignum

1 Like
#20

Theo mình thì từ đầu bài có N và H <1,000,000 nên có thể xảy ra trường hợp có 1,000,000 quả bóng và có quả nhận độ cao là 1,000,000

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?