Từ 1 tới 8 trên tổng số 8 kết quả

Đề tài: Điền các số 0 , 1 vào ma trận ...

  1. #1
    No Avatar
    mr.gren Khách

    Red face Điền các số 0 , 1 vào ma trận ...

    Viết chương trình điền vào bảng N*N gồm các số 0 và 1 sao cho bất kỳ hình vuông K*K nào cũng chứa đúng S số 1 .
    (1<= N < 40 )
    Ví dụ
    N = 3
    K = 2
    S = 1
    ta tìm được :

    0 0 0
    0 1 0
    0 0 0

    Mọi người giúp em bài này với ...!!!

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài này hình như thi giải tin năm 2006 T_T, bài dễ kiếm điểm nhất :
    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3.  
    4. const int SIZE = 20;
    5.  
    6. bool get_n_k_s( int& _n, int& _k, int& _s ) {
    7.     std::cout << "Enter N, K, S ( seperated by space ) : ";
    8.     std::cin >> _n >> _k >> _s;
    9.     if( _n <= 0 || _k <= 0 || _s <= 0
    10.                 || _k > _n || _s > _n * _n
    11.     ) {
    12.         std::cout << "\n Invalid input data. Program end !\n";
    13.         return false;
    14.     }
    15.     return true;
    16. }
    17.  
    18. void put_one( int grid[ ][ SIZE ], int N, int K, int S )
    19. {
    20.     int cnt = 0;
    21.     for( int o = ( 2*K - 2 ); o >= 0; --o ) {
    22.         for( int row = K - 1; row >= 0 && row >= ( o - K + 1 ); --row ) {
    23.             int col = o - row;
    24.             for( int o1 = row; o1 < N; o1 += K ) {
    25.                 for( int o2 = col; o2 < N; o2 += K ) {
    26.                     grid[ o1 ][ o2 ] = 1;
    27.                 }
    28.             }
    29.             if( ++cnt == S )
    30.                 return;
    31.         }
    32.  
    33.     }
    34.  
    35.  
    36. }
    37.  
    38. void show_grid( int grid[ ][ SIZE ], int SIZ, const char* g_name ) {
    39.     std::cout << g_name << "\n";
    40.     for( int x = 0; x < SIZ; ++x ) {
    41.         for( int y = 0; y < SIZ; ++y ) {
    42.             std::cout << grid[ x ][ y ] << " ";
    43.         }
    44.         std::cout << "\n";
    45.     }
    46.     std::cout << "\n\n";
    47. }
    48.  
    49. int main() {
    50.     int N, // matrix of size N*N
    51.         K, // inner square of size K*K
    52.         S; // number of '1' in a K*K square
    53.  
    54.     int grid[ SIZE ][ SIZE ] = { 0 };
    55.     if( get_n_k_s( N, K, S ) )
    56.     {
    57.         show_grid( grid, N , "show grid " );
    58.         put_one( grid, N, K, S );
    59.         show_grid( grid, N, "show grid " );
    60.     }
    61. }

  3. #3
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Bài này hình như thi giải tin năm 2006 T_T, bài dễ kiếm điểm nhất :
    Kiểm tra lại thuật toán nhá. ; ) )


  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Thanks T_T, sai thật, thôi sữa lại cho đúng cái đã nhưng code này không tối ưu, có 1 số trường hợp đặc biệt, để có thời gian tui sẽ suy nghĩ lại sau :
    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3.  
    4. const int SIZE = 20;
    5.  
    6. bool get_n_k_s( int& _n, int& _k, int& _s ) {
    7.     std::cout << "Enter N, K, S ( seperated by space ) : ";
    8.     std::cin >> _n >> _k >> _s;
    9.     if( _n <= 0 || _k <= 0 || _s <= 0
    10.                 || _k > _n || _s > _k * _k
    11.     ) {
    12.         std::cout << "\n Invalid input data. Program end !\n";
    13.         return false;
    14.     }
    15.     return true;
    16. }
    17.  
    18. void put_one( int grid[ ][ SIZE ], int N, int K, int S )
    19. {
    20.     int cnt = 0;
    21.     for( int o = K - 1; o >= 0; --o ) {
    22.         for( int row = K - 1; row >= 0 && row >= ( o - K + 1 ); --row ) {
    23.             int col = o - row;
    24.             for( int o1 = row; o1 < N; o1 += K ) {
    25.                 for( int o2 = col; o2 < N; o2 += K ) {
    26.                     grid[ o1 ][ o2 ] = 1;
    27.                 }
    28.             }
    29.             if( ++cnt == S )
    30.                 return;
    31.         }
    32.  
    33.     }
    34.  
    35.  
    36. }
    37.  
    38. void show_grid( int grid[ ][ SIZE ], int SIZ, const char* g_name ) {
    39.     std::cout << g_name << "\n";
    40.     for( int x = 0; x < SIZ; ++x ) {
    41.         for( int y = 0; y < SIZ; ++y ) {
    42.             std::cout << grid[ x ][ y ] << " ";
    43.         }
    44.         std::cout << "\n";
    45.     }
    46.     std::cout << "\n\n";
    47. }
    48.  
    49. int main() {
    50.     int N, // matrix of size N*N
    51.         K, // inner square of size K*K
    52.         S; // number of '1' in a K*K square
    53.  
    54.     int grid[ SIZE ][ SIZE ] = { 0 };
    55.     if( get_n_k_s( N, K, S ) )
    56.     {
    57.         show_grid( grid, N , "show grid " );
    58.         put_one( grid, N, K, S );
    59.         show_grid( grid, N, "show grid " );
    60.     }
    61. }

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Better one , but still not sure it's 100% correct though :
    C++ Code:
    1. void put_one( int grid[ ][ SIZE ], int N, int K, int S ) {
    2.     int cnt = 0;
    3.     int o;
    4.     S > ( 2*K ) / 3 ? o = K - 1 : o = 2*K - 2;
    5.     for( ; o >= 0; --o ) {
    6.         for( int row = K - 1; row >= 0 && row >= ( o - K + 1 ); --row ) {
    7.             int col = o - row;
    8.             for( int o1 = row; o1 < N; o1 += K ) {
    9.                 for( int o2 = col; o2 < N; o2 += K ) {
    10.                     grid[ o1 ][ o2 ] = 1;
    11.                 }
    12.             }
    13.             if( ++cnt == S )
    14.                 return;
    15.         }
    16.  
    17.     }
    18. }
    Kiểm tra lại thuật toán nhá. ; ) )
    Cậu cho tui giải tham khảo giải thuật của cậu luôn nhé ! Cám ơn trước !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 27-10-2008 lúc 03:05 PM.

  6. #6
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    Mặc định Điền các số 0 , 1 vào ma trận ...

    Có giải thuật gì đâu, cứ duyệt qua tất cả các ô vuông con thôi.

    C++ Code:
    1. #include "stdafx.h"
    2.  
    3. const int SIZE = 20;
    4.  
    5. int N, K, S;
    6. int matrix[SIZE][SIZE];
    7. int traveled[SIZE][SIZE] ;
    8.  
    9. bool get_n_k_s();
    10. void show_grid();
    11. int  numOneOfSquare(int i, int j);
    12. void addOnetoSquare(int i, int j, int& nOne);
    13. void fillMaxtrix();
    14.  
    15. void main(void)
    16. {
    17.     while (1)
    18.     {
    19.         memset(matrix[0], 0, SIZE*SIZE*4);
    20.         memset(traveled[0], 0, SIZE*SIZE*4);
    21.  
    22.         if (get_n_k_s())
    23.         {
    24.             fillMaxtrix();
    25.             show_grid();
    26.         }
    27.     }
    28. }
    29.  
    30. void fillMaxtrix()
    31. {
    32.     for (int i = 0; i <= N - K; ++i)
    33.     {
    34.         for (int j = 0; j <= N - K; ++j)
    35.         {
    36.             int nOne = numOneOfSquare(i, j);
    37.             addOnetoSquare(i, j, nOne);
    38.         }
    39.     }
    40.        
    41. }
    42.  
    43. int numOneOfSquare(int iR, int jC)
    44. {
    45.     int res = 0;
    46.     for (int i = iR; i < K + iR; ++i)
    47.     {
    48.         for (int j = jC; j < K + jC; ++j)
    49.         {
    50.             res += matrix[i][j];
    51.         }
    52.     }
    53.     return res;
    54. }
    55.  
    56. void addOnetoSquare(int iR, int jC, int& nOne)
    57. {
    58.     for (int i = iR; i < K + iR; ++i)
    59.     {
    60.         for (int j = jC; j < K + jC; ++j)
    61.         {
    62.             if (!traveled[i][j])
    63.             {
    64.                 traveled[i][j] = 1;
    65.                 if (nOne < S)
    66.                 {
    67.                     matrix[i][j] = 1;
    68.                     ++nOne;
    69.                 }
    70.             }
    71.         }
    72.     }
    73. }
    74.  
    75. bool get_n_k_s()
    76. {
    77.     cout << "Enter N, K, S: ";
    78.     cin >> N >> K >> S;
    79.     cout << endl;
    80.  
    81.     if( N <= 0 || K <= 0 || S <= 0
    82.                 || K > N || S > K * K)
    83.     {
    84.         cout << "\n Invalid input data. Program end !\n";
    85.         return false;
    86.     }
    87.  
    88.     return true;
    89. }
    90.  
    91. void show_grid()
    92. {
    93.     for( int x = 0; x < N; ++x ) {
    94.         for( int y = 0; y < N; ++y ) {
    95.             cout << matrix[x][y] << " ";
    96.         }
    97.         cout << "\n";
    98.     }
    99.     cout << "\n----------------------\n\n";
    100. }

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Có giải thuật gì đâu, cứ duyệt qua tất cả các ô vuông con thôi.
    - Sao không có ?
    - Với dữ liệu 3 2 1 chỉ có 1 số 1, code cậu cho ra 4 số 1, vì vậy mới cần tối ưu cậu à ! Đơn giản thế làm sao thi học sinh giỏi được

  8. #8
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Sao không có ?
    - Với dữ liệu 3 2 1 chỉ có 1 số 1, code cậu cho ra 4 số 1, vì vậy mới cần tối ưu cậu à ! Đơn giản thế làm sao thi học sinh giỏi được
    Là tớ nói code của tớ chả có giải thuật gì cả, chứ không phải chỉ code của cậu.
    Tớ không biết giải thuật của cậu tối ưu tới đâu.
    Code này tớ suy nghĩ và code trong 15 và chạy đúng, còn cậu...

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

  1. Trao đổi liên kết, trao doi logo, Text Link với các webforumblog (free)
    Gửi bởi nguyenlam14990 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 31
    Bài viết cuối: 13-03-2012, 11:53 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