CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT: ỨNG DỤNG XE BUS (C++)

C++/ BÀI: ỨNG DỤNG XE BUS

Bạn Bách đang muốn thống kê số xe buýt thường ghé trạm trong khu vực gần nhà mình. Bách đi tới các trạm xe buýt ở gần nhà mình là tại mỗi trạm Bách ghi lại danh sách các tuyết xe buýt ghé trạm đó. Sau khi ghi xong Bách được một danh sách dài rất lộn xộn và tốn nhiều giấy mực. Bách nhận thấy thường mỗi tuyến xe buýt chỉ cần ghi 01 lầ và nếu có nhiều tuyến có số hiệu liên tiếp nhau ví dụ như 150, 151, 152 thì Bách có thể ghi là 150-152 thay vì ghi cả 3 số hiệu 3 tuyến đó ra. Cũng cần lưu ý là chỉ ghi nào có 03 tuyến với số hiệu liên tiếp trở lên thì mới tiết kiệm được giấy mực.

Hãy viết chương trình giúp Bách ghi danh sách các tuyến xe buýt một cách gọn gàng hơn.

Input

Dòng đầu tiên chứa số nguyên N, 1≤N≤1000, Đây là số lượng tuyến xe buýt ghé trạm.. Dòng tiếp theo chứ Nsố nguyên cách nhau bởi khoảng trắng giá trị trong khoảng từ 1 đến 1000, đây là số hiệu các tuyến xe buýt có ghé trạm đó.

Output

In ra màn hình danh sách các tuyến xe buýt một cách ngắn gọn nhất và số hiệu tuyến đã được sắp tăng dần.

Sample Input 1Sample Output 1
35
531 942 140 19 560 121 341 348 487 776 326 688 361 962 539 465 350 97 853 957 775 865 660 290 317 926 471 582 395 529 444 239 419 847 589
19 97 121 140 239 290 317 326 341 348 350 361 395 419 444 465 471 487 529 531 539 560 582 589 660 688 775 776 847 853 865 926 942 957 962
246
782 731 516 857 326 206 816 840 345 998 133 344 95 141 669 598 499 408 171 439 347 596 932 84 160 978 558 611 844 382 819 449 699 178 119 835 153 227 44 902 201 472 403 503 414 852 396 176 1000 970 225 761 521 671 377 109 490 417 696 363 30 42 34 200 78 847 350 191 384 386 895 422 912 134 913 574 75 222 968 322 930 985 905 462 820 710 740 555 676 418 150 340 664 789 830 717 587 797 776 302 506 575 139 824 770 218 78 801 214 532 237 55 693 571 668 638 85 778 123 395 205 272 353 297 431 324 567 506 922 750 103 253 540 446 842 544 477 488 425 723 530 363 565 401 511 609 657 999 374 534 27 730 868 47 898 918 981 93 260 752 622 956 43 825 896 484 729 235 740 848 852 477 934 22 819 777 139 16 777 85 545 307 103 971 396 556 1 815 644 934 872 561 966 160 249 568 415 814 304 10 277 148 817 433 858 72 894 515 857 816 420 774 594 581 875 230 455 665 377 5 249 682 909 305 768 307 60 393 300 797 790 140 837 796 212 27 720 742 849 728 642 957 301 519 311 921
1 5 10 16 22 27 30 34 42-44 47 55 60 72 75 78 84 85 93 95 103 109 119 123 133 134 139-141 148 150 153 160 171 176 178 191 200 201 205 206 212 214 218 222 225 227 230 235 237 249 253 260 272 277 297 300-302 304 305 307 311 322 324 326 340 344 345 347 350 353 363 374 377 382 384 386 393 395 396 401 403 408 414 415 417 418 420 422 425 431 433 439 446 449 455 462 472 477 484 488 490 499 503 506 511 515 516 519 521 530 532 534 540 544 545 555 556 558 561 565 567 568 571 574 575 581 587 594 596 598 609 611 622 638 642 644 657 664 665 668 669 671 676 682 693 696 699 710 717 720 723 728-731 740 742 750 752 761 768 770 774 776-778 782 789 790 796 797 801 814-817 819 820 824 825 830 835 837 840 842 844 847-849 852 857 858 868 872 875 894-896 898 902 905 909 912 913 918 921 922 930 932 934 956 957 966 968 970 971 978 981 985 998-1000

CODE THAM KHẢO: C++

  1. #include <iostream>
  2. using namespace std;
  3. void Nhap(int [], int );
  4. void Xuat(int [], int );
  5. void Insertion_sort(int [], int );
  6. void NganGon(int [],int &);
  7. int main()
  8. {
  9.     int n;
  10.     cin>>n;
  11.     int *M=new int[n];
  12.     Nhap(M,n);
  13.     NganGon(M,n);
  14.     Insertion_sort(M,n);
  15.     Xuat(M,n);
  16.     return 0;
  17. }
  18. void Nhap(int M[], int n)
  19. {
  20.     for(int i=0; i<n; i++)
  21.     {
  22.         cin>>M[i];
  23.     }
  24. }
  25. void Xuat(int M[], int n)
  26. {
  27.     int i, j;
  28.     for(i=0; i<n; i++)
  29.     {
  30.         int kt=1;
  31.         for(j=i; j<n-1; j++)
  32.         {
  33.             if(M[j]+1==M[j+1])
  34.             {
  35.                 kt++;
  36.             }
  37.             else
  38.             {
  39.                 break;
  40.             }
  41.         }
  42.         if(kt<3)
  43.         {
  44.             cout<<M[i]<<” “;
  45.         }
  46.         else
  47.         {
  48.             cout<<M[i]<<“-“<<M[i+kt-1]<<” “;
  49.             i=i+kt-1;
  50.         }
  51.     }
  52. }
  53. void Insertion_sort(int M[], int n)
  54. {
  55.     int vt=0;
  56.     int x;
  57.     for (int i=1; i<n; i++)
  58.     {
  59.         x=M[i];
  60.         for (vt=i; (vt>0)&&(M[vt-1]>x); vt–)
  61.         {
  62.             M[vt]=M[vt-1];
  63.         }
  64.         M[vt]=x;
  65.     }
  66. }
  67. void NganGon(int M[],int &n)
  68. {
  69.     for(int i=0; i<n-1; i++)
  70.     {
  71.         int j=i+1;
  72.         while (j<n)
  73.         {
  74.             if (M[i]!=M[j])
  75.             {
  76.                 j++;
  77.             }
  78.             else
  79.             {
  80.                 for(int k=j; k<n-1; k++)
  81.                 {
  82.                     M[k]=M[k+1];
  83.                 }
  84.                 n–;
  85.             }
  86.         }
  87.     }
  88. }

Be the first to comment

Leave a Reply

Your email address will not be published.


*