Code sinh hoán vị kế tiếp bị kết quả sai

NobiKin · April 25, 2018, 3:23am

Đây là đề bài ạ

Còn đây là code của em , sao e test trên Dev C++ thì đúng mà sub lại Kết quả sai ạ ?

Ninh_Le · March 5, 2015, 4:53pm

Chào bạn,
Nếu bạn làm đúng cả 3 test của đề bài thì 99% là đúng rồi đấy.
Điểm mấu chốt là đề bài bảo: số có 80 chữ số, mà bạn khai báo có a[80] thì ra đáp số sai là phải rồi. ít nhất phải khai báo a[81] chứ

Mình thấy thuật toán bạn hơi lạ thì phải, cái này phải dùng thuật toán sinh hoán vị tiếp theo. Bạn làm theo thuật toán này thử xem:

Liệt kê theo thứ tự tăng dần.
Tìm vị trí đầu tiên tính từ bên phải qua mà dãy mất tính giảm dần (vị trí k);
Hoán đổi vị trí k với các phần tử sau k vừa đủ lớn hơn k ;
Sắp xếp các phần tử sau k theo chiều tăng dần ;
X = <3,2,6,5,4,1> --> vì a[2] = 2 nên k = 2
–> vì a[5]=4 vừa đủ lớn hơn a[2]=2 nên swap(a[2],a[4]) được <3,4,6,5,2,1>
–> sắp xếp tăng dần : <3,4,1,2,5,6>

Mình có tí nhận xét ngoài lề :

hàm swap là một hàm trong C++ tự định nghĩa sẵn, nên bạn không cần phải cài đặt nó làm gì nhé.
Bạn viết hàm đổi string sang int hơi dài, bạn có thể áp dụng:

 int convert(char c) {
    return (int) c - 48 ;
}

3. Mình thấy, bạn khai báo string dạng mảng kí tự thì đã dùng kiểu chuổi của C, dó đó bạn có thể dùng hàm atoi để chuyển chuỗi sang int nhanh chóng rồi.
Tuy nhiên, bài này bạn không cần xây dựng hàm chuyển đổi string sang int đâu, vì kiểu kí tự (char) cũng so sánh được mà, đâu cần phải đổi sang số int.

Cuối cùng, bạn có thể tham khảo code của mình vừa làm (submit ra đáp số đúng rồi nên bạn yên tâm )

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int test ;
  
    cin>>test ;
    for(int t= 0 ;  t<test ; t++ ) {
		int stt ; 
		string so;
		cin>>stt>>so;
	

        int i = so.size() -2 ;
        while (so[i] >= so[i+1]) {
            i-- ;
        }
        if(i== -1) {
            cout<<stt<<" BIGGEST" <<endl ;
        }
        else {
            int big = 0 ;
            char min = '9' ;
            int imin = i ;
            for(int  k = i+1 ; k<so.size() ; k++) {
               if(so[k] > so[i] && so[k] <=min ) {
                    min = so[k] ;
                    imin = k ;
               }
            }
            // doi 2 ki tu voi nhau
            char temp = so[i] ;
            so[i] = so[imin] ;
            so[imin] = temp ;
            // sap xep lai chuoi phía sau
            for(int k = i+1 ; k<so.size() -1  ; k++) {
                for(int j = k+1 ;  j <so.size() ; j++) {
                    if(so[k] > so[j]) {
                        temp = so[k] ;
                        so[k] = so[j] ;
                        so[j] = temp ;
                    }
                }
            }
                cout<<stt<<" " <<so<<endl ;
        }

    }


    return 0;
}

Gio · March 5, 2015, 4:41pm

Dùng luôn cái next_permutation đi

bool has_next =next_permutation(s.begin(),s.end());
if(has_next) cout<<stt<< " "<<s<<endl;
else cout<<stt<<" BIGGEST\n";

Ninh_Le · March 5, 2015, 4:40pm

Quên mất, bạn quả nhiên cao minh
p/s: có luyện ACM/ICPC gì không mà pro thế

Gio · March 5, 2015, 4:43pm

Học thuật toán chơi thôi. Thích hoc toán hơn