Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

Đề tài: Đề olympic C++ | Hoán vị các chữ số trên C++??

  1. #1
    Ngày gia nhập
    04 2009
    Bài viết
    19

    Mặc định Đề olympic C++ | Hoán vị các chữ số trên C++??

    Các pác giúp mình với .

    Đây là đề : Tìm tất cả các số có sáu chữ số sao cho tất cả các tích của nó với 2, 3, 4, 5, 6 đều viết được từ số ban đầu bằng cách hoán vị các chữ số

    Đây là hướng giải thuật của mình :

    Kiểm tra 1 số a thì bạn tạo 1 mảng để lưu các chữ số có trong a,rồi tạo 1 mảng thứ 2 để lưu tích của
    a với 2 ,bạn sắp xếp 2 mảng tăng dần rồi kiểm tra xem 2 mảng có bằng nhau ko,nếu đúng thì xuất mảng 1
    ra sau khi kiểm tra a xong thì bạn reset lại 2 mảng để dùng cho số tiếp theo,bạn làm tương tự với các
    số còn lại.


    Còn đây là code mình đã làm, còn nhiều sai sót , mong bạn lại giúp mình hoàn chỉnh cái code này :

    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    
    
    
    void sorta(int a[])
    {
        int i, j, temp;
        for (i = (6 - 1); i >= 0; i--)
            {
            for (j = 1; j <= i; j++)
                {
                if (a[j-1] > a[j])
                    {
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                    }
                 }
            }
    }
    void sortb(int b[])
    {
        int i, j, temp;
        for (i = (6 - 1); i >= 0; i--)
            {
            for (j = 1; j <= i; j++)
                {
                if (b[j-1] > b[j])
                    {
                    temp = b[j-1];
                    b[j-1] = b[j];
                    b[j] = temp;
                    }
                 }
            }
    }
    
    int check(long n)
    {
        int a[6],b[6];
        long temp=n;
        for(int i=0;i<6;i++)
            {
                a[i]=temp%10;temp/=10;}
                temp=n*2;
                for(int i=0;i<6;i++)
                {
                    b[i]=temp%10;temp/=10;
                    sorta(a);sortb(b);
                    for(int i=0;i<6;i++)
                    {
                        if(a[i]!=b[i])
                        {
                            //cout<<"ko phai la so do";
                            for(int j=0;j<6;j++)
                            a[j]=-1;
                            return 0;
                            //cout<<a[j];
                        }
    
                    }
                    return 1;
                    //cout<<"la so do";
                }
    }
    void main()
    {
        long m,numbers[99999999];
        long n,i;
        //cout<< "nhap chieu dai :"; cin>>n;
        for(long i=100000;i<999999;i++)
         cin>numbers[i] =i ;
         //cin>>n;
        cout<<"\nket qua : "<<check(n);
    	cin>>n;
    
    }

  2. #2
    Ngày gia nhập
    03 2009
    Nơi ở
    Hà Nội
    Bài viết
    74

    sao bạn lại phải làm cực nhọc thế.ko cần phải sắp xếp 2 mảng đó đâu.ta chỉ cần so sánh các phần tử của mảng thôi.
    cho 2 vòng for chạy các phần tử của 2 mảng.
    nếu với 1 phần tử ở mảng 1 có 1 phần tử ở mảng 2 bằng nó thì cho phần tử nó bằng -1(đánh dấu đã được sử dụng) nếu không tồn tại thì trả về 0 luôn và thoát hàm.
    cuối hàm ta cho return 1; thế là được mà. code của mình đây:
    Code:
    int kiem_tra(int n,int k){
        int a1[6],a2[6];
        int tmp=n*k,i=0,j,kt;
        if(n*6>999999) return 0;
        while(n>0){
            a1[i]=n%10;
            a2[i]=tmp%10;
            i++;
            n/=10;
            tmp/=10;
        }
        for(i=0;i<6;i++){
            kt=0;
            for(j=0;(j<6)&&(kt==0);j++){
                if(a1[i]==a2[j]) {kt=1;
                //printf("%d %d",a[i],
                a2[j]=-1;}
            }
            if (kt==0) return 0;
        }
        return 1;
    }

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    25

    Làm theo cách của bạn minhgiang thì giả sử mảng 1 có 2 phần tử là số 6, mảng 2 có 3 phần tử là số 6. Vậy vẫn thỏa sao? Mình nghĩ là ko.

  4. #4
    Ngày gia nhập
    04 2008
    Bài viết
    336

    hiện thực hóa ý tưởng của bạn nguyenjimi thành code:
    C Code:
    1. #include<stdio.h>
    2. #include<stdlib.h>
    3.  
    4. int isEqual(char *a,char *b,int num)
    5. {
    6.     for(int i = 0; i<num;++i)
    7.         if(a[i]!=b[i])
    8.             return 0;
    9.     return 1;
    10. }
    11.  
    12. int compare(const void* a,const void* b)
    13. {
    14.     return *(char*)a - *(char*)b;
    15. }
    16.  
    17. int isValid(long lNumber)
    18. {
    19.     char strIn[7],strTmp[7];
    20.  
    21.     sprintf(strIn,"%ld",lNumber);
    22.     qsort(strIn,6,1,compare);   //skip '\0'
    23.  
    24.     for(int i = 2; i<=6; ++i)
    25.     {
    26.         long temp = lNumber*i;
    27.         sprintf(strTmp,"%ld",temp);
    28.         qsort(strTmp,6,1,compare);
    29.         if(!isEqual(strIn,strTmp,6))
    30.             return 0;
    31.     }
    32.  
    33.     return 1;
    34. }
    35.  
    36. int main()
    37. {
    38.     long soLan = 999999/6+1;
    39.     for(long i = 100000; i<soLan;++i)
    40.         if(isValid(i))
    41.             printf("%d\n",i);
    42.     system("pause");
    43.     return 0;
    44. }

    bài giải ngắn gọn nhất là ...
    C Code:
    1. #include<stdio.h>
    2. int main()
    3. {
    4.     printf("%d\n",142857);
    5.     return 0;
    6. }

    code ra gió bão

  5. #5
    Ngày gia nhập
    11 2008
    Bài viết
    21

    Thử tìm 1 cách để không phải đổi số sang mảng, cuối cùng lại ra code điên loạn thế này:

    Mình lưu số luôn dưới dạng mảng và khi thực hiện phép nhân thì tính ra từng chữ số nếu sai 1 chữ số cho phăng teo luôn, trường hợp chậm nhất thì sẽ tương đương với đổi số sang mảng.

    C++ Code:
    1. #include<iostream>
    2. #include<stdlib.h>
    3. using std::cout;
    4. char a[6];
    5.  
    6. void display()
    7. {
    8.     for( int i=0; i<6; ++i )
    9.         cout << (int)a[i];
    10. }
    11.  
    12. int isin( char x, char b[])
    13. {
    14.     for(int i=0; i<6; ++i)
    15.     if( x == b[i] )
    16.     {
    17.         b[i] = 10;
    18.         return 1;
    19.     }
    20.     return 0;
    21. }
    22.  
    23. int match()
    24. {
    25.     char b[6];
    26.     for(int i = 2; i<=6; ++i)
    27.     {
    28.         char tmp, j, nho = 0;
    29.         memcpy(b,a,6);
    30.         for(j = 5; j >= 0 ; --j)
    31.         {
    32.             tmp = a[j]*i+nho;
    33.             div_t thuong = div(tmp,10);
    34.             if( !isin( thuong.rem, b ) )
    35.                 return 0;
    36.             nho = thuong.quot;
    37.         }
    38.  
    39.         if(nho) return 0;
    40.     }
    41.     return 1;
    42. }
    43.  
    44. void for_loop(char k = 1)
    45. {
    46.     for ( a[k] = 0 ; a[k] <= 9 ; ++a[k])
    47.     if( k == 5 )
    48.     {  
    49.         if( match()) display();
    50.     }
    51.     else for_loop( k+1 );
    52. }
    53.  
    54. int main()
    55. {
    56.     a[0]=1;
    57.     for_loop();
    58.     return 0;
    59. }

    Test trên code::block mất 0,015s ( cách của bạn 6220119 mất 0,062s )
    Đã được chỉnh sửa lần cuối bởi regist : 05-05-2009 lúc 07:52 PM.

  6. #6
    Ngày gia nhập
    04 2008
    Bài viết
    336

    Mặc định Đề olympic C++ | Hoán vị các chữ số trên C++??

    ko phải cách của mình đâu, mình thấy ý tưởng hay nên cố gắng biến nó thành code thôi (tuy nhiên với 6 số thì kiểm tra bằng 2 vòng lặp lồng nhau sẽ nhanh hơn sắp xếp rồi kiểm tra) :P

    cách của regist thì nhanh hơn 100% vì có can thiệp vào quá trình nhân để kiểm tra trực tiếp.
    code ra gió bão

  7. #7
    Ngày gia nhập
    03 2009
    Nơi ở
    Hà Nội
    Bài viết
    74

    Trích dẫn Nguyên bản được gửi bởi hunter_hikaru Xem bài viết
    Làm theo cách của bạn minhgiang thì giả sử mảng 1 có 2 phần tử là số 6, mảng 2 có 3 phần tử là số 6. Vậy vẫn thỏa sao? Mình nghĩ là ko.
    hjxxxx, sao bạn lại nói thế.bạn đã đọc giải thuật của mình chưa vậy:
    giả sử đầu có 2 chữ số 6: số sau có 3;
    thì với số 6 đầu ta tìm được vị trí ở số thứ 2 cũng là 6.rồi ta thay đổi luôn chỗ đó thành -1.vậy thì hết 2 chữ số 6 ở số thứ nhất ta vẫn còn 1 chữ số 6 ở số thứ 2. vậy thì sẽ có một chữ số ở số thứ nhất ko bằng chữ số nào ở số thứ 2.và return 0.

    http://ebook.here.vn
    trang web cung cấp đề thi,tài liệu ôn thi đại học.

  8. #8
    Ngày gia nhập
    01 2008
    Bài viết
    3

    Các bác có thể ghi chú thích trên các dòng code được không? Em chưa hiểu mấy chỗ

  9. #9
    Ngày gia nhập
    04 2012
    Bài viết
    42

    @6220119: Tại sao phải lấy 999999/6+1 ạ. Em chưa hiểu lắm. :P
    C Code:
    1. while (!silly)
    2.     cout<<"Study everything !";

  10. #10
    Ngày gia nhập
    07 2009
    Nơi ở
    Thị trấn Lâm Thao - Phú Thọ
    Bài viết
    86

    thì số có 6 chữ số lớn nhất là 999999 mà bạn
    khi nhân với 6 nó vẫn là số có 6 chữ số nên ???
    bạn hiểu chưa vậy bạn
    Ngô Hùng Cường
    Birthday: 14/4/1986 - Cư ngụ: Thị trấn Lâm Thao - Phú Thọ
    kidteam@gmail.com
    Yahoo ID: cuong_dhbk2004
    0989696971
    0915696971

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

  1. Tài liệu lập trình C Cần đề cương hướng dẫn Olympic tin học C
    Gửi bởi Doreamon9x trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 0
    Bài viết cuối: 22-07-2010, 10:51 AM
  2. Các đề thi Olympic qua các năm
    Gửi bởi cafelanh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 17
    Bài viết cuối: 06-06-2010, 07:22 PM
  3. Xin hỏi về việc học olympic tin học
    Gửi bởi saolion trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 2
    Bài viết cuối: 04-09-2009, 01:13 PM
  4. Đề thi Olympic Quốc Nội !
    Gửi bởi Template trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 15
    Bài viết cuối: 27-11-2008, 05:37 PM
  5. Xin Ebook tương tự các đề thì olympic tin học
    Gửi bởi bathong trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 3
    Bài viết cuối: 30-10-2008, 10:33 AM

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