test đúng rồi hay quá. của mình n=100 thì chuvi=40
#21
Đã gửi 21-07-2014 - 20:14
#22
Đã gửi 21-07-2014 - 21:15
test đúng rồi hay quá. của mình n=100 thì chuvi=40
ừ, bạn thử làm theo cách toán học xem: tìm min a+b khi biết ab>=n;
#23
Đã gửi 21-07-2014 - 21:53
ừ, bạn thử làm theo cách toán học xem: tìm min a+b khi biết ab>=n;
Lâu lâu lên VMF, thấy forum thuật toán hay hay, vào phá đám chút.
Có thể chứng minh: $\text{minimize}\{a + b\} \text{with } a \times b = n \iff \text{minimize}\{|a - b|\}$ (hình như bạn làm theo cách này)
Time complexity: $O(1)$
Một bài đơn giản:
Phân tích số $\frac{a}{b}$ dưới dạng ($k$ càng nhỏ càng tốt):
$$\frac a b = \sum_{i=1}^{k} \frac 1 {M_k} = \frac 1 {M_1} + \frac 1 {M_2} + ... + \frac 1 {M_k}$$
Thêm một bài này nữa:
Cho tập số tự nhiên $A$ chứa $n$ số tự nhiên, n dòng dạng
i j x
tức $A_i - A_j \ge x$
Tìm một tập nghiệm thoả mãn, nếu không có in ra IMPOSSIBLE
Bài viết đã được chỉnh sửa nội dung bởi ilovelife: 21-07-2014 - 22:02
- nghethuat102 yêu thích
God made the integers, all else is the work of man.
People should not be afraid of their goverment, goverment should be afraid of their people.
#24
Đã gửi 22-07-2014 - 20:24
Mình cũng chẳng chắc là tối ưu hay chưa, không thì sắp xếp đi!
Bài 3 dùng thuật toán Lùa bò về chuồng liệu có tối ưu không bạn nhỉ?
Naive: O(n^2)
Sắp xếp:
Merge sort / Heap Sort / Quick Sort: $O(n log n)$
Radix Sort: $O(kn)$ (k là số chữ số trung bình)
Dùng cấu trúc dữ liệu:
Map / Set (red-black tree): $O(n log n)$
Hash Table: $O(n)$
Với dữ liệu ~1000 thì sort lại là đủ, và nếu bạn không gặp đen thì hash table là nhanh nhất.
God made the integers, all else is the work of man.
People should not be afraid of their goverment, goverment should be afraid of their people.
#25
Đã gửi 22-07-2014 - 20:53
Bạn giải thích rõ hơn chút đi
Cách sort lại:
Mình dùng C++ (dạng mã giả) để minh hoạ vì có sẵn STL hơn:
int arr[n + 1];// đánh số từ 0
arr[n] = số integer nhỏ nhất;
int res[n];
int cnt = 0;
sort(arr, arr + n) // sort dãy theo thứ tự tăng dần
for (int i = 0; i < n; i++) { // đánh số từ 0
if (arr[i] != arr[i + 1]){
res[cnt] = arr[i];
cnt++;
}
if (cnt == 0){
cout << 1 << endl; // output kết quả
cout << arr[n];
} else {
cout << cnt << endl;
for(int i = 0; i < cnt; ++i) cout << res[i] << " ";
}
}
Cách dùng set:
int n;
cin >> n;
int in;
set<int> s;
for(int i = 0; i < n; ++i){
cin >> in;
s.insert(s);
}
// s.size() và cách số trong s là kết quả.
Cách dùng hash table, tương tự cách dùng set
Bài viết đã được chỉnh sửa nội dung bởi ilovelife: 22-07-2014 - 20:53
God made the integers, all else is the work of man.
People should not be afraid of their goverment, goverment should be afraid of their people.
#26
Đã gửi 22-07-2014 - 21:05
ừ, bạn thử làm theo cách toán học xem: tìm min a+b khi biết ab>=n;
Chào Nghethuat102 bạn xem lai bài viên sỏi, mình chứng minh qua toán học thì n=100 chu vi nhỏ nhất phải là 40 chứ không phải 42 bạn à
#27
Đã gửi 22-07-2014 - 21:16
Chào Nghethuat102 bạn xem lai bài viên sỏi, mình chứng minh qua toán học thì n=100 chu vi nhỏ nhất phải là 40 chứ không phải 42 bạn à
^^, cái đó mình biết rồi ,nên đã sửa code lại!
bạn viết thêm 1 câu:
if a*b>=n+a then b:=b-1;
dưới cái câu
if a*b>=n+a then a:=a-1;
#28
Đã gửi 22-07-2014 - 22:04
ok! vậy là chu vi nhỏ nhất khi nó là hình vuông
Không phải lúc nào cũng như vậy:
Ví dụ: 10 thì chu vi nhỏ nhất sẽ là 7 x 2
Nói cách khác nếu $n$ là số chính phương thì $a = b = \sqrt n$
$a = b = \left \lfloor \sqrt n \right \rfloor$ // phần nguyên của căn $n$
while $a * b < n$:
$a++$
if $a * b < n$:
$b++$
# Mình chưa kiểm tra, có thể sửa cái while kia = if luôn mà không gây ảnh hưởng
Bài viết đã được chỉnh sửa nội dung bởi ilovelife: 22-07-2014 - 22:08
God made the integers, all else is the work of man.
People should not be afraid of their goverment, goverment should be afraid of their people.
#29
Đã gửi 22-07-2014 - 22:05
ok! vậy là chu vi nhỏ nhất khi nó là hình vuông
đó chỉ là một trường hợp thôi,
vd: nếu n=20 thì chu vi nhỏ nhất là 18,tức (4+5)*2
#30
Đã gửi 23-07-2014 - 08:25
Bạn hướng dẫn cụ thể bài 5 tớ với nha, hì chưa hiểu lắm thuật toán ngắn mà hiệu quả lên khó quá
Cái vòng for chạy từ 0-..., nếu chuyển vào toán, bạn cứ xem như là giả sử:
vd:
d=7; k=5;
giả sử số cần tìm có 3 chữ số;
tức là nó có dạng (ab7) vs ab7 là số có 3 chữ số nghe!
như thế thì: (ab7)x5 =(7ab) ( theo đề );
phân tích ra: 10x5x(ab)+7x5 = 700 +(ab)
=> (ab)x(10x5-1) = 700-7x5;
=> (ab) = (700-7x5)/(10x5-1);
thay d,k vào: (ab)= (d*100-d*k)/(k*10-1);
chú thích: d*100 vì ở đây ta giả sử số có 3 chữ số).
Bài viết đã được chỉnh sửa nội dung bởi nghethuat102: 23-07-2014 - 08:28
#31
Đã gửi 23-07-2014 - 10:25
Cái vòng for chạy từ 0-..., nếu chuyển vào toán, bạn cứ xem như là giả sử:
vd:
d=7; k=5;
giả sử số cần tìm có 3 chữ số;
tức là nó có dạng (ab7) vs ab7 là số có 3 chữ số nghe!
như thế thì: (ab7)x5 =(7ab) ( theo đề );
phân tích ra: 10x5x(ab)+7x5 = 700 +(ab)
=> (ab)x(10x5-1) = 700-7x5;
=> (ab) = (700-7x5)/(10x5-1);
thay d,k vào: (ab)= (d*100-d*k)/(k*10-1);
chú thích: d*100 vì ở đây ta giả sử số có 3 chữ số).
Mình hiểu rồi thế mà tối qua ngồi cắn bút mãi, toán học chán vài hì
Bài số đối xứng! bạn thử coi
Một số được gọi là số đối xứng khi các chữ số của nó đối xứng qua tâm.
Yêu cầu : Cho một số nguyên dương x, hãy tìm số đối xứng lớn hơn và gầnx nhất.
Ví dụ : Các số 5, 44, 212, 71217 là những số đối xứng.
Cho một số x = 371, số đối xứng lớn hơn và gần x nhất là 373
#32
Đã gửi 23-07-2014 - 11:10
Mình hiểu rồi thế mà tối qua ngồi cắn bút mãi, toán học chán vài hì
Bài số đối xứng! bạn thử coi
Một số được gọi là số đối xứng khi các chữ số của nó đối xứng qua tâm.
Yêu cầu : Cho một số nguyên dương x, hãy tìm số đối xứng lớn hơn và gầnx nhất.
Ví dụ : Các số 5, 44, 212, 71217 là những số đối xứng.
Cho một số x = 371, số đối xứng lớn hơn và gần x nhất là 373
#33
Đã gửi 23-07-2014 - 13:38
Bạn nói qua hướng dẫn ột chut nha, mình đọc vất vả quá
Text đúng chính là hướng dẫn rồi!
Bài này xử lý trên xâu:
vd: 123 =>202
chết cha, dông, đợi chút lát làm cho
#34
Đã gửi 23-07-2014 - 16:30
Ừ
Xâu đối xứng.
Yêu cầu: Xâu S ko quá 200 kí tự. Kiểm tra xem S có phải xâu đối xứng hay ko.
Nếu ko phải thì cho biết số kí tự ít nhất cần thêm vào S để S trờ thành xâu đối xứng.
VD:
RADAR
Dx
TOMATO cần thêm 3 kí tự
Code này mình viết có vẻ vẫn còn sai nhiều test bạn xem qua họ cái nha
Var st,s:string;
#35
Đã gửi 24-07-2014 - 00:18
st trên chưa có giá trị ??
Mình sửa lại như thế này bạn test hộ mình xem có sai không nha
Bài viết đã được chỉnh sửa nội dung bởi hocpascal: 24-07-2014 - 00:31
#36
Đã gửi 24-07-2014 - 22:03
Chìa khóa
Giả thiết có N hộp được đặt tên A1,A2,....,AN (3<=N<=200). Mỗi hộp được khóa bởi một khóa riêng. Người ta bỏ vào mỗi hộp một chìa khóa và khóa các hộp từ A3 cho đến AN. sau đó mở hai hộp A1 và A2 lấy các chìa khóa ra. Nếu những chìa khóa này mở được một số hộp nào đó, người ta sẽ lấy các chìa khóa ra từ đó và mở tiếp các hộp khác. Nếu cuối cùng người ta mở được hết các hộp, thì các chìa khóa gọi là bố trí tốt.
Hỏi có bao nhiêu cách bố trí tốt các chìa khóa?
vd: N=6 có 240 cách bố trí tốt!
Giúp tôi thuật toán bài này với!
#37
Đã gửi 25-07-2014 - 10:23
Mình nghĩ bài này chắc không khó nhưng mình đọc hiểu đề ít quá. mình chỉ có một test đó thôi
Vậy là khó rồi, sợ 200 sẻ tràn dữ liệu, nếu làm như đệ quy quay lui 200 là con số lớn và có khi mất cả tiếng để duyệt qua text 200
#38
Đã gửi 26-07-2014 - 13:26
quả thật là tràn dữ liệu đó bạn!! Bài khác đi, bài này số nhỏ khoảng 20 thì làm dc hoặc là text của bạn có vấn đề rồi!
Số nguyên tố tương đương là gì?. Sntđ là số nguên tố có các ước nguyên tố như nhau.
Vd: 12 và 18 đều có các ước nguyên tố là 2,3
15 và 75 đều có các ước nguyên tố là 3,5
Số 12 và 60 không nguyên tố tương đương vì 60 có ước nguyên tố là 5 mà số 12 không có.
Mình code tìm hai số như dưới nhưng không nghĩ ra cách tìm tất cả các số nguyên tố tđ <=999999. Bạn sửa hộ mình nha! thank!
uses crt;
var a,b,i,j,max:word;
nt,uocnt:boolean;
begin
clrscr;
write('Nhap a, b:'); readln(a,b);
if a>=b then max:=a else max:=b;
for i:=2 to max div 2 do
begin
nt:=true;
for j:=2 to trunc(sqrt(i)) do {kt cac snt}
if i mod j = 0 then
begin
nt:=false;
break;
end;
if nt then {kt cac snt do co phai la uoc cua a,b khong}
begin
uocnt:=true;
if ((a mod i = 0)and(b mod i<>0)) or ((a mod i<>0)and(b mod i=0))
then uocnt:=false;
if not uocnt then break;
end;
end;
if uocnt then write('La snt tuong duong')
else write('Khong phai snt tuong duong');
readln
end.
#39
Đã gửi 26-07-2014 - 21:20
mình viêt được rồi nhưng nhiều lắm hì
Bạn thử bài này xem
Bài 2: Xét một số N có 4 chữ số và không phải tất cả các chữ số đều giống nhau. Phép tính độ lệch được thực hiện như sau:
· Tạo số thứ nhất N1 bằng cách xếp các chữ số theo trình tự giảm dần
· Tạo số thứ hai N2 bằng cách xếp các chữ số theo trình tự tăng dần (nếu có chữ số 0 ở đầu thì N2 sẽ không phải là số có 4 chữ số)
· Tính hiệu N1-N2 và gán lại cho N
Các bước trên được thực hiện cho đến khi nhận được số N là 6174 hoặc 0
Ví dụ: Nếu N=1023
· Ở bước 1: N1=3210, N2=123, N=N1-N2=3087
· Ở bước 2: N1=8730, N2=378, N=N1-N2=8352
· Ở bước 3: N1=8532, N2=2358, N=N1-N2=6174
Vậy ta cần thực hiện 3 lần biến đổi
Yêu cầu: Hãy xác định số lần biến đổi thực hiện theo yêu cầu trên.
Dữ liệu: Nhập từ bàn phím số nguyên dương N (N đảm bảo có 4 chữ số, không phải tất cả các chữ số đều giống nhau và N khác 6174. Không cần kiểm tra dữ liệu nhập)
Kết quả: Ghi ra màn hình số lần biến đổi tương ứng với số N
Ví dụ:
Dữ liệu nhập: 5364
Kết quả in ra: 3
#40
Đã gửi 27-07-2014 - 08:56
Bạn thử bài này xem
Bài 2: Xét một số N có 4 chữ số và không phải tất cả các chữ số đều giống nhau. Phép tính độ lệch được thực hiện như sau:
· Tạo số thứ nhất N1 bằng cách xếp các chữ số theo trình tự giảm dần
· Tạo số thứ hai N2 bằng cách xếp các chữ số theo trình tự tăng dần (nếu có chữ số 0 ở đầu thì N2 sẽ không phải là số có 4 chữ số)
· Tính hiệu N1-N2 và gán lại cho N
Các bước trên được thực hiện cho đến khi nhận được số N là 6174 hoặc 0
Ví dụ: Nếu N=1023
· Ở bước 1: N1=3210, N2=123, N=N1-N2=3087
· Ở bước 2: N1=8730, N2=378, N=N1-N2=8352
· Ở bước 3: N1=8532, N2=2358, N=N1-N2=6174
Vậy ta cần thực hiện 3 lần biến đổi
Yêu cầu: Hãy xác định số lần biến đổi thực hiện theo yêu cầu trên.
Dữ liệu: Nhập từ bàn phím số nguyên dương N (N đảm bảo có 4 chữ số, không phải tất cả các chữ số đều giống nhau và N khác 6174. Không cần kiểm tra dữ liệu nhập)
Kết quả: Ghi ra màn hình số lần biến đổi tương ứng với số N
Ví dụ:
Dữ liệu nhập: 5364
Kết quả in ra: 3
định lý 6174, bài chưa bao giờ mình làm chuẩn dc thuật toán:
Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: pascal
Toán thi Học sinh giỏi và Olympic →
Hình học →
Chứng minh rằng O,I,P thẳng hàng.Bắt đầu bởi quochuy50618, 17-11-2021 pascal |
|
|||
Vấn đề chung của Diễn đàn →
Góp ý cho diễn đàn →
Nên thêm mục Tin họcBắt đầu bởi michealdzung, 21-10-2017 tin học, pascal, lập trình và . |
|
|||
Cửa sổ Diễn Đàn Toán Học →
Câu lạc bộ ngoại khóa →
Góc Tin học →
PASCAL: in ra màn hình nghịch thế của hoán vị và tìm số (Cần giúp)Bắt đầu bởi Higo Akira, 16-03-2017 pascal, tinhoc |
|
|||
Cửa sổ Diễn Đàn Toán Học →
Câu lạc bộ ngoại khóa →
Góc Tin học →
Chuỗi gần đúngBắt đầu bởi The Dark Hunter, 13-08-2016 pascal |
|
|||
Cửa sổ Diễn Đàn Toán Học →
Câu lạc bộ ngoại khóa →
Góc Tin học →
bài tập pascal toán học mong các bạn giúp đỡBắt đầu bởi vansonqtqb, 27-07-2016 pascal |
|
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh