Sắp xếp chữ số c++

• 
• Diễn đàn
• LẬP TRÌNH C++ | LẬP TRÌNH C | LẬP TRÌNH C++0X
• Thắc mắc lập trình C/C++/C++0x
• Bài tập C Sắp xếp các chữ số trong n (Ko dùng mảng, chuỗi))

1. Sắp xếp các chữ số trong n (Ko dùng mảng, chuỗi))

   Cho mình hỏi cách giải bài này thế nào với:

   Nhap n; sắp xếp các chữ số trong n theo thứ tự tăng dần ,( Ko được dùng mảng or chuỗi )

   vd: n= 3126 ==> 1236

   ---

2. Cái này phải dùng sắp xếp chèn.
   Bạn xác định chữ số ở vị trí nào dựa vào phép chia liên tiếp cho mười, rồi chèn, cái khó là tìm ra vị trí tương ứng với bậc bao nhiêu thôi. Mình ngại code vì trời hơi nóng, thông cảm nha bạn.

   Hi vọng giúp được bạn.

   ---

3. Bạn sử dụng 2 hàm này, rồi sắp xếp như trong mảng xem sao.
   

   Code:

   #include 
   #include 
   #include 
   
   using namespace std;
   //dao phan tu i, i-1 trong bien n
   // vd m=34787, i=3 => n=34877
   //		54321
   int swap(int n, int i)
   {
   	int m, k, l;	//luu gia tri pt thu i, i+1
   	m = n/(int)pow((float)10, i-1)%10;	// lay gia tri o phan tu thu i
   	k = n/(int)pow((float)10, i-2)%10;	// phan tu thu i-1
   	l = n%((int)pow((float)10,i-2));	// cac phan tu sau do
   	n = n/(int)pow((float)10, i);		// tinh nguoc lai sau khi doi
   	n = n*10+k;
   	n = n*10+m;
   	n = n*(int)pow((float)10,i-2)+l;
   	return n;
   }
   // >0 neu pt i > pt i-1
   // nguoc lai
   int cmp(int n, int i)
   {
   	int m, k, l;	//luu gia tri pt thu i, i+1
   	m = n/(int)pow((float)10, i-1)%10;	// lay gia tri o phan tu thu i
   	k = n/(int)pow((float)10, i-2)%10;	// phan tu thu i-1
   	return m - k;
   }

   ---

4. Một cách giải:

   đọc số (bằng phương pháp %10 và /10), tìm chữ số nhỏ nhất, lưu ý là có thể nhiều hơn một
   ghi ra số mới với số nhỏ nhất này
   tiếp tục đọc số, tìm chữ số nhỏ nhất và lớn hơn chữ số hiện tại.

   Giải thuật này bắt buộc phải chạy vòng lặp nhiều lần

   1. // hàm đọc một số (so), tìm chữ số nhỏ nhất (nn) và lớn hơn một trị (min)

   2. // hàm trả về số lần xuất hiện của chữ số này

   4. int ChuSoNhoNhat(int so, int min, int *nn, int *sl)

   5. {

   6. int cs;

   7. *nn = 10; // min hiện tại: 10 lớn hơn chữ số lớn nhất (9)

   8. *sl = 0; // số lần xuất hiện

   9. while (so > 0)

   10. {

   11. cs = so % 10; // chữ số kế tiếp

   12. if (cs > min)  // chữ số này lớn hơn trị min giới hạn

   13. {

   14. if (cs < *nn)  // nhỏ hơn min hiện tại, chọn min mới

   15. {

   16. *nn = cs;

   17. *sl = 1;

   18. }

   19. else if (cs == *nn)  (*sl)++;  // bằng min hiện tại, tăng số lần xuất hiện

   20. }

   21. so /= 10;

   22. }

   23. return *sl;

   24. }

   27. // code sắp xếp chữ số

   29. int soCuaToi = 82966217;

   31. int soLan, cs1 = -1, cs2 = 0;

   32. int soDaSapXep = 0;

   34. while (ChuSoNhoNhat(soCuaToi, cs1, &cs2, &soLan))  // nếu trả về số lần == 0, không còn chữ số > cs1

   35. {

   36. for (int i = 1; int <= soLan; i++)   soDaSapXep = soDaSapXep * 10 + cs2;

   37. cs1 = cs2;

   38. }

   40. // code này chưa chạy thử, chỉ dùng để diễn tả thuật toán

   
   TB tôi không hiểu nếu không dùng chuỗi, mảng thì làm sao chứa được số này:
   32105507 ==> 00123557 ????

   Cách duy nhất là tính đến đâu, in đến đấy

   Code:

   if (soCuaToi == 0) printf("0");
   else
   while (ChuSoNhoNhat(soCuaToi, cs1, &cs2, &soLan))  // nếu trả về số lần == 0, không còn chữ số > cs1
   {
      for (int i = 1; int <= soLan; i++)   prntf("%d",i);
      cs1 = cs2;
   }

   ---

5. Nguyên bản được gửi bởi VoTichSu

   TB tôi không hiểu nếu không dùng chuỗi, mảng thì làm sao chứa được số này:
   32105507 ==> 00123557 ????

   Cách duy nhất là tính đến đâu, in đến đấy

   Ko có j là ko thể, chỉ là do mình chưa nghĩ ra mà thui! Đùa xí cho vui

   
   Mình xin đóng góp 1 cách giải quyết thỏa y/c đề bài ko dùng mảng & chuỗi:
   Code như sau (đã test):
   

   1. #include

   2. #include

   3. int temp(int n, int index) { return n / index % 10; }

   4. void swap(int &n, int index1, int index2)

   5. {

   6. int temp1 = temp(n, index1);

   7. n = n / (index1 * 10) * (index1 * 10) + temp(n, index2) * index1 + n % index1;

   8. n = n / (index2 * 10) * (index2 * 10) + temp1 * index2 + n % index2;

   9. }

   10. void bubblesort(int &n)

   11. {

   12. int i, j, n1, n2;

   13. for(i = 1, n1 = n; n1 > 10; i *= 10, n1 /= 10)

   14. for(j = i * 10, n2 = n1 / 10; n2 > 0; j *= 10, n2 /= 10)

   15. if( temp(n, i) < temp(n, j))

   16. swap(n, i, j);

   17. }

   18. void main()

   19. {

   20. int n=3216;

   21. bubblesort(n);

   23. }

   Phân tích sơ qua 1 chút: gặp 1 bài toán sắp xếp ta có rất nhiều thuật toán để giải quyết, nhưng với bài này ta ko quan trọng về thuật toán sắp xếp nên mình chọn thuật toán đơn giản nhất (bubble sort) để mô tả.
   - Cái khó của bài toán là ko dc dùng mảng, vì vậy mình sẽ định nghĩa biến index như sau:
   n = 3126 = 3*1000+1*100+2*10+6*1
   từ phân tích trên ta nhận thấy có 1 biến tăng theo quy luật mà ta có thế thay cho index trong mảng (1,10,100,1000,...) tương ứng với(hàng đơn vị, hàng chục, hàng trăm, hàng nghìn, ...)
   - Hàm temp trả về 1 con số tương ứng với giá trị trong mảng tại vị trí index
   vd: n=3126; temp(n,100) <=> n[2]=1 (lưu ý mảng ở đây có index ngược tức tăng dần từ cuối về đầu)
   - Hàm swap hoán đổi vị trí 2 số ứng với index1 và index2
   vd: n=3126; swap(n,100,1000) -> n=1326
   - Hàm bubblesort thực hiện việc sắp xếp với thuật toán nổi bọt

   ---

6. Sắp xếp các chữ số trong n (Ko dùng mảng, chuỗi))

   Nguyên bản được gửi bởi mrvu.mlt

   Ko có j là ko thể, chỉ là do mình chưa nghĩ ra mà thui!
   ...
   void main()
   {
   int n=3216;
   bubblesort(n);
   cout< }
   ...

   đã nói là thuật toán tính ra số n sẽ không in được số có 0 ở giữa
   nếu n = 3216 thì sau khi sort, n = 1236
   nếu n = 32016 thì sau khi sort, cũng cho ra n = 1236

   Nếu muốn in ra 02136 thì bắt buộc phải thêm một biến ghi nhớ lại độ lớn của số n ban đầu.

   Một cách khác là chơi mánh, thay vì sắp xếp lớn dần thì ta sắp xếp nhỏ dần (32016 -> 63210). Lúc in thì in đảo ngược lại.

   ---

Các đề tài tương tự

1. Trả lời: 2

   Bài viết cuối: 05-04-2013, 03:58 PM

2. Trả lời: 1

   Bài viết cuối: 29-06-2011, 12:02 AM

3. Trả lời: 0

   Bài viết cuối: 07-08-2010, 05:18 PM

4. Trả lời: 6

   Bài viết cuối: 21-04-2010, 09:55 AM

5. Trả lời: 5

   Bài viết cuối: 05-01-2010, 05:04 PM

Quyền hạn của bạn

• Bạn không thể gửi đề tài mới
• Bạn không thể gửi bài trả lời
• Bạn không thể gửi các đính kèm
• Bạn không thể chỉnh sửa bài viết của bạn

• Tìm hiểu luật lệ tham gia diễn đàn

• BB code: On
• Mặt cười: On
• [IMG] code: On
• [VIDEO] code is On
• HTML code: Off