お知らせ:このサイトは閉鎖します。移転先についてはhttp://projectroom.jphttp://haukun.projectroom.jpを参照ください。
新約聖書 マタイによる福音書朗読TwitterBot @BibleJP_Matt好きなテキストをiPhoneの壁紙に。iPhone用Webアプリ「ポステラ」聖書 創世記朗読TwitterBot @BibleJP_GenCodeOfCelestia -数学的壁紙配信サイト-

Problems 302. Count on Cantor

公開日:2010/12/27 (Mon)

概要

出展

https://www.spoj.pl/problems/CANTON/

簡単な解説

(1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4...)と続く数列があるとする。
この時、n番目は何なのかを求める。

(主観的な)ジャンル

数学的なアルゴリズム

(主観的な)難易度 5段階

☆☆(標準)

所感

問題文の表がヒントです。ここからどうやってn番目を導き出すかがポイントです。
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1

ごり押しでも解けそうな気がするのですが、スマートな方法を探してみることにしました。

考察

n番目がどの辺り位置するのかの検討をつける必要があります。
1引いて、2引いて、3引いて...で負の数になるまで計算してもいいのですが、時間かかりそうなので、個人的にNGです。

まず、「分母+分子」が同じ値のものをグループにします。
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1
今回の数列はこのグループを、左下に進む⇒左上に進む⇒左下に進む...を繰り返していることが分かります。
グループに属する分数の数は、1つ、2つ、3つ...と増えて行きますので、台形の公式を使うとm番目のグループまでに存在する分数の個数を求めることができます。

(上底+下底)*高さ/2=台形の面積
(1+m)*m/2=分数の個数
(m*m)+m=分数の個数*2 ...(1)

(1)で、分数の個数をsとすると、

m^2 + m - 2s = 0

と展開できます。これは2次方程式なので、解の公式が使用可能です。

m = (-1 + √(1 + 8s)) / 2

となります。グループ番号mは正の値なので、-√の方はあり得ないので却下です。
sは、今回の入力値nと同値ですので、これによって求まった値を小数点以下切り上げればmが確定できます。

グループ番号mが求まれば、nがそのグループで何番目にいるのかを求めることが可能となります。
グループ内の分数は、「分母+分子=m+1」ということが分かっているので、これによりn番目の分数を特定することが可能です。

解答例

//////////////////////////////////////////////////
//
//  Sphere Online Judge
//      302. Count on Cantor
//      Problem code:   CANTON
//
//      Author  : Hau-kun
//      Date    : 2010/12/27
//
//////////////////////////////////////////////////
//  accepted
//      TIME    0.00
//      MEM     1.6M
//      LANG    C
//////////////////////////////////////////////////

#include 
#include 

#define FORMAT_OUTPUT "TERM %d IS %d/%d\n"

//  プロトタイプ宣言
void AnalyzeContor(void);

//////////////////////////////////////////////////
//  メイン関数
////////////////////////////////////////////////////
int main(void)
{
    int i = 0;
    int nLoopMax = 0;       //  問題数

    //  問題数読み取り
    scanf("%d", &nLoopMax);
    
    //  問題数分、処理を繰り返す
    for(i = 1; i <= nLoopMax; i++)
    {
        AnalyzeContor();
    }

    return 0;
}

//////////////////////////////////////////////////
//  データ出力関数
//////////////////////////////////////////////////
void AnalyzeContor(void)
{
    int nInput = 0;
    int nGroup = 0;
    int nOrder = 0;

    //  データの入力
    scanf("%d", &nInput);

    //  データがどのグループにいるかを求める。
    nGroup = ceil((-1 + sqrt((double)1 + 8 * nInput)) / 2); //  cf.解の公式

    //  データが、グループ内の何番目にいるのか求める。
    nOrder = ((nGroup * nGroup + nGroup) - (nInput * 2)) / 2;

    //  データが、分母の減少グループか、分子の減少グループかを求め、結果を出力する
    if(nGroup % 2 == 0)
    {
        //  分母の減少グループ
        printf(FORMAT_OUTPUT, nInput, nGroup - nOrder, nOrder + 1);
    }
    else
    {
        //  分子の減少グループ
        printf(FORMAT_OUTPUT, nInput, nOrder + 1, nGroup - nOrder);
    }
}

このコンテンツのタグ: アルゴリズム C言語 プログラミング


このコンテンツへのコメント

コメント無し

コメントフォーム
名前
(Max15文字)
削除パスワード
(Max15文字)
コメント
(Max1500文字)
コメントを投稿する※投稿する場合はこちらをチェック。
コメントを削除する※名前欄にIDを、削除パスワードに投稿時のパスワードを入れることで削除できます。

2013年もよろしくお願いいたします!

合計 228095
12/12 20
12/11 99
12/10 80
12/09 93
12/08 78
12/07 93
12/06 98
1,722,379
478 時間
19
5.4616
[とても昔]
アプリ内は良さそうだけど、ホーム画面はのっぺりしちゃうなぁ…。
[とても昔]
次のOSXそう来たかw
[とても昔]
SurfaceProゲットなう。思ったよりタッチ画面が使いやすかった。キーボードの縦幅短いから、画面と近いからかな。 これで、Win8/iOS/Androidアプリどれでも作れる! http://t.co/7CXQCVVao5
[とても昔]
じわじわくるw >RT
[とても昔]
スタジオレンタルして、15年ぶりにピアノを弾くなう。あとステージアも初体験できて良かった。近場で便利。フロッピーじゃなく、USBでレジストいけるのね。楽譜もネットで購入→印刷できるので、買いに行く必要すらなくなった。すごい時代。 http://t.co/9gRBztS2UB
@Hau_kun

Twitterでマタイによる福音書を読んでみませんか @BibleJP_Mattで朗読中 Twitterで創世記を読んでみませんか @BibleJP_Genで朗読中 好きなテキストをiPhoneの壁紙に。iPhone用Webアプリ「ポステラ」

区切り線
はぅ君プロジェクトについて

管理人はぅ君の運営する個人ポータルサイトです。
技術・思想・ソフトウェア・その他もろもろをコンテンツとして公開していきます。
ご意見・ご感想・要望は、各コンテンツのコメントか、お問い合わせよりどうぞ。

Rss 1.0 RSS1.0のフィード