Đến nội dung


Chú ý

Do trục trặc kĩ thuật nên diễn đàn đã không truy cập được trong ít ngày vừa qua, mong các bạn thông cảm.

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Lập trình Pascal

pascal

  • Please log in to reply
Chủ đề này có 200 trả lời

#21 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã gửi 21-07-2014 - 20:14

test đúng rồi hay quá. của mình n=100 thì chuvi=40



#22 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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 ilovelife

ilovelife

    Sĩ quan

  • Thành viên
  • 371 Bài viết
  • Giới tính:Nam
  • Đến từ:Đang ở ẩn

Đã 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

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 ilovelife

ilovelife

    Sĩ quan

  • Thành viên
  • 371 Bài viết
  • Giới tính:Nam
  • Đến từ:Đang ở ẩn

Đã 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 ilovelife

ilovelife

    Sĩ quan

  • Thành viên
  • 371 Bài viết
  • Giới tính:Nam
  • Đến từ:Đang ở ẩn

Đã 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 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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 ilovelife

ilovelife

    Sĩ quan

  • Thành viên
  • 371 Bài viết
  • Giới tính:Nam
  • Đến từ:Đang ở ẩn

Đã 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 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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

 
var s:string;    i,j:integer;
begin
write('s=');
readln(s);
           while s[1]='0' do delete(s,1,1);
          for i:=1 to length(s) do
          if s[i] in['0'..'9'] then j:=j+1;
          if j<length(s) then exit;
          for i:=1 to length(s) div 2 do
             if s[i]>s[length(s)-i+1] then s[length(s)-i+1]:=s[i]
             else if s[i]<s[length(s)-i+1] then
              begin
              s[i]:=chr(ord(s[i])+1);
              s[length(s)-i+1]:=s[i];
              for j:=i+1 to length(s)-i do
               s[j]:='0';
              end;
          writeln(s);
readln;
end.


#33 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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;

  i,dem,l,j:longint;
BEGIN
  read(s);
    dem:=0;
  l:=length(st);
  i:=1;
  While (i<=l) do
    Begin
      If (st[i]<>st[l-i+1]) then
        Begin
        insert(st[i],st,l-i+2); inc(dem);
        l:=length(st);
        end;
        inc(i);
        end;
        write(dem);
        readln;
        readln
        end.


#35 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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

 Var st:string;
  i,dem,l :l ongint;
BEGIN
  read(st);
    dem:=0;
      l:=length(st);
  i:=1;
  While (i<=l) do
    Begin
      If (st[i]<>st[l-i+1]) and (st[i] <> st[l-i]) then
      begin
      insert(st[i],st,l-i+2);
      inc(dem);
      l:=length(st);
      end
      else
      If (st[i]<>st[l-i+1]) and (st[i] = st[l-i]) then
      begin
      insert(st[l-i+1],st,i);
      inc(dem);
      l:=length(st);
      end ;
       inc(i);
     end;
      write('so ki tu it nhat can then  ', dem);
        readln;
        readln
        end.

Bài viết đã được chỉnh sửa nội dung bởi hocpascal: 24-07-2014 - 00:31


#36 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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 hocpascal

hocpascal

    Trung sĩ

  • Thành viên
  • 109 Bài viết

Đã 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 nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Nam
  • Đến từ:đâu?
  • Sở thích:code, code, code and code!

Đã 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:

var n,d,t,p:integer;
  function sx(n:integer):integer;
   var  i,j:integer; c,s:string;
   begin
      str(n,s);
      for i:=1 to length(s)-1 do
       for j:=i+1 to length(s) do
            if (s[i]<s[j]) then
                 begin
                 c[1]:=s[i];
                 s[i]:=s[j];
                 s[j]:=c[1];
                 end;
       val(s,j,i);
       sx:=j;
       c:='';
       for i:=length(s) downto 1 do
          c:=c+s[i];
       val(c,p,i);
   end;
  begin
  repeat
   write('n=');
   readln(n);
  until (n<>6174);
  d:=0;
  while (n<>6174) do
   begin
   p:=0;
   d:=d+1;
   t:=sx(n);
   n:=t-p;
   end;
  writeln(d);
  readln;
  end.
 Không có kiểm tra điều kiện!






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh