スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ある算数オリンピックの問題を解くC++プログラムの例

標準テンプレートライブラリ (STL) を使用した C++ の簡単なサンプルプログラムとして。

算数オリンピックの問題は以下のとおり。

5×5 のマス目に 6 個の○を次の条件を満たすように書きます。

条件:各行・各列に少なくとも 1 個は○を書く。同じマスには 2 個以上の○を書くことはできない。

このとき、6 個の○を書く方法は全部で何通りありますか。

元ネタは、以下の記事にある問題 7。

はてな若手エンジニアが「算数オリンピック」の問題を解いてみた

問題の解答は 4200 になります (空白部分をドラッグすると読めます)。

プログラム例

すべての○の書き方について、問題の条件を満たすかどうかを確かめています。

ポイントは next_permutation の部分で、25 個のマスから○を記入するための 6 個のマスを選び出す操作を行うのに使用しています。要は組合せ (combination) ですが、それを 0 と 1 からなる列の並べ替えとして考えています。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// ○の書き方が問題の条件を満たすかどうか
bool check(
  const vector<int> &board, 
  const unsigned int cols, 
  const unsigned int rows ); 

int main()
{
  const unsigned int circs = 6;  // ○の個数
  const unsigned int cols  = 5;  // 列数(1行あたりのマス目の数)
  const unsigned int rows  = 5;  // 行数(1列あたりのマス目の数)
  const unsigned int cells = cols * rows;  // マス目の総数

  vector<int> board(cells);  //  マス目のボード
  int count = 0;  //  条件を満たす○の書き方の数

  // 0, ... , 0, 1, 1, 1, 1, 1, 1 なる列の作成
  for ( int i = 0; i < cells ; i++ ) {
    if ( i < cells - circs ) {
      board[i] = 0;
    }
    else {
      board[i] = 1;
    }
  }

  // 全ての○の書き方について条件をチェック
  do {
    if ( check(board, cols, rows) ) { count++; }
  } while ( next_permutation(board.begin(), board.end()) );

  // 解答の出力
  cout << count << endl;

  return 0;
}

bool check(
  const vector<int> &board, 
  const unsigned int cols, 
  const unsigned int rows ) 
{
  // 各行が空白かどうか
  for ( int i = 0; i < rows; i++ ) {
    bool isBlank = true;
    for ( int j = 0; j < cols; j++ ) { 
      if ( board[i*cols+j] == 1 ) { 
        isBlank = false; 
        break;
      }
    }
    if ( isBlank ) { return false; }
  }

  // 各列が空白かどうか
  for ( int j = 0; j < cols; j++ ) {
    bool isBlank = true;
    for ( int i = 0; i < rows; i++ ) { 
      if ( board[i*cols+j] == 1 ) { 
        isBlank = false; 
        break;
      }
    }
    if ( isBlank ) { return false; }
  }

  return true;
}

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。