初心者です。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
pon

初心者です。

#1

投稿記事 by pon » 15年前

このprogramming(C言語)の間違いを指摘してください。お願いします。

http://www1.axfc.net/uploader/Sc/so/95276.c

このprogramは情報オリンピック2009-2010の予選4
(http://www.ioi-jp.org/joi/2009/2010-yo- ... t4/2010...を解こうと作ったのですが、全く正常に動きません。
Errorログを見て、自分で分かる限り書き変えたのですが、これ以上分からないので、よろしくお願いします。


自分がやりたいこととしては、くっつけてできるすべての数を配列にいれて、配列をあとで昇順に並べて同じのを省いて個数を数えるということをしたいのですが
まだ、配列を昇順に並べて~は実装していません。

softya

Re:初心者です。

#2

投稿記事 by softya » 15年前

マルチポストですよね?
http://detail.chiebukuro.yahoo.co.jp/qa ... 1138396526
ここの規約を見直してみてください。

pon

Re:初心者です。

#3

投稿記事 by pon » 15年前

すいません。マルチポストです、と明記するのを忘れていました…

softya

Re:初心者です。

#4

投稿記事 by softya » 15年前

規約に書いてあると思いますが、こちらだけでなく知恵袋にも明記してください。

pon

Re:初心者です。

#5

投稿記事 by pon » 15年前

知恵袋にマルチの件補足させていただきました

softya

Re:初心者です。

#6

投稿記事 by softya » 15年前

まず、問題のリンクが参照出来ませんのでちゃんとリンクをお願いします。
問題文が分からないで何をしたいか分かりません。

それと、ぱっと見た限りは、文字と文字列の区別が出来ていません。どのぐらいC言語で勉強したか教えてください。現状、この問題を解くにはC言語の経験不足としか思えません。

下記のサイトの14章の文字列を扱う方法を読んでください。
http://homepage3.nifty.com/mmgames/c_guide/
14章の練習問題は簡単に解けますか? 画像

pon

Re:初心者です。

#7

投稿記事 by pon » 15年前

http://www.ioi-jp.org/joi/2009/2010-yo- ... yo-t4.html
すいません。コレです

strcatではなく、sprintfを使えば良いのでしょうか?
sprintfを使えばあらかじめk*k!個の予備を作る必要がなさそうですが

pon

Re:初心者です。

#8

投稿記事 by pon » 15年前

http://www1.axfc.net/uploader/Sc/so/95478.c
上のlinkを読んで作った改訂版です。
何がいけないのでしょうか

たいちう

Re:初心者です。

#9

投稿記事 by たいちう » 15年前

予選とはいえナントカオリンピックの問題なので初心者には難しいでしょう。
いきなり完璧なものを作ろうとしないで、まずは(n, k) = (4, 2)の場合専用の
プログラムを作ってはいかがでしょうか。

# 面白い問題を紹介してくれてありがとうございます。

たいちう

Re:初心者です。

#10

投稿記事 by たいちう » 15年前

scanf("%d",n);

scanf("%d",&n);

sprintf(answer[e],"%s%s%s%s",a,b,c,d);

sprintf(answer[e],"%d%d%d%d",card[a],card,card[c],card[d]);

試してませんが、この類の間違いを直せば、正しい答えにずいぶん近づくと思います。
それとソートがデタラメ。

dic

Re:初心者です。

#11

投稿記事 by dic » 15年前

VC++6 ではコンパイルできませんがC
Cだとできるのかな?・・・

softya

Re:初心者です。

#12

投稿記事 by softya » 15年前

間違っているところ。
(1)コンパイルエラー
for文の対応が間違ってます。

(2)ローカル変数が巨大すぎる。
char answer[10000][10000];

(3)値受け取り時の書き方が間違い。
scanf("%d",&n);
scanf("%d",&k);

(4)値受け取り時の書き方が間違い。
char card[15];
scanf("%s",&card);
cardは15個の文字を受け取る配列であって、15個の文字列を受け取る配列ではありません。

(5)sprintfの使い方の間違い。
sprintf(answer[e],"%s%s",a,b);
 ↓
sprintf(answer[e],"%s%s",card[a],card);

(6)カード4毎の時に同じカードが出ないガードが無い。

(7)ソート?している理由が分からない。
同じ数値を排除するのが目的ですよね?
まず、文字列はstrcmpで同じかどうか比較してください。
アルゴリズムとしては、自分より後に同じ数値が出てこない数値をカウントすれば個数を求めることが出来ると思います。

たいちう

Re:初心者です。

#13

投稿記事 by たいちう » 15年前

入力部分以外のプログラムは作ったけど、
一枚のcardはcharやcharの配列ではなく、
1つの整数で表す方が簡単だと思うな。
行き詰ったら試してみてください。

pon

Re:初心者です。

#14

投稿記事 by pon » 15年前

みなさんありがとうございます。
配列を先に並び替えることで配列の次の番号のと等しいかを比べていくだけで良いので手数が減るかなと思ったのと等しいのは数えず異なるのだけ数えるのが大変に思えたのですが
まず、配列の比較する方法は配列の1から比較する、で良いですか?

forの間違いとは何ですか?

配列の数が大きいのはあとでなおすよていですが、エラーを取り除こうと思っていたので。ご指摘ありがとうございます。
このプログラムにおけるcharとintの違いは何ですか?

pon

Re:初心者です。

#15

投稿記事 by pon » 15年前

http://www1.axfc.net/uploader/Sc/so/95551.c

一応コンパイルできるようになりましたが、かなり遅いです。
どうすれば効率の良いプログラムになるでしょうか

たいちう

Re:初心者です。

#16

投稿記事 by たいちう » 15年前

> forの間違いとは何ですか?

"2010/03/23(火) 13:47"のリンク先のプログラムはコンパイルが通りませんでしたので、
そのことでしょう。


> このプログラムにおけるcharと intの違いは何ですか?

元のプログラムでは、1つのカードをchar型の変数で表すつもりなのか、
char型の配列、つまり文字列で表すつもりなのか、不明でした。
(どっちとみなしても間違いがありました)
そのため文字列で扱うよりも整数で扱った方が楽だよ、という意味でした。


> 一応コンパイルできるようになりましたが、かなり遅いです。
> どうすれば効率の良いプログラムになるでしょうか

効率の話の前に確認ですが、コンパイルが通っただけですか?
正しい答えが出せるようになったのですか?
原則として、効率の事を考える前に正しく動くプログラムを作る必要があります。

pon

Re:初心者です。

#17

投稿記事 by pon » 15年前

コンパイルは通りました。プログラムが全然終了しないので、もう少し効率の良いプログラムにしないといけないのかと。

たいちう

Re:初心者です。

#18

投稿記事 by たいちう » 15年前

> コンパイルは通りました。プログラムが全然終了しないので、
> もう少し効率の良いプログラムにしないといけないのかと。

効率が悪いから終了しないのですか?
正しいプログラムではないから終了しないのではないですか?
どうやって確認します?

pon

Re:初心者です。

#19

投稿記事 by pon » 15年前

確認の仕方は全く分かりませんが、最後のprintf~を除いても終了しませんでした
ループ関数が無限ループしているところはなさそうなのですが 

たいちう

Re:初心者です。

#20

投稿記事 by たいちう » 15年前

↓こんなのがありましたが。

for(b=a+1;b<e;a++)

GannRock

Re:初心者です。

#21

投稿記事 by GannRock » 15年前

最新のtest.cを入手致しました。

まず、基本的な問題としてコードが醜いです。
main()内に全て実装しているし、
コメントも無いので解読が困難です。

関数化し、適宜コメントを付けてください。

配列境界を超えている個所があります。

106行目の

for(b=a+1;b<e;a++)
でbの代わりに誤ってaをインクリメントしている為

110行目の
if(answer[a][c] != answer[c])

が不正な所をアクセスします。

この種のバグを素早く検出する為に
assertを使って境界チェックすべきです
http://www.geocities.jp/ky_webid/c/059.html

例えば
110行の前に

assert(a < 6000 && b < 6000 && c < 10);

と入れておくのです。
すると条件が成立していないとプログラムが停止し
行番号も表示されます。

これを配列アクセスの随所に入れておきます。
これだけで随分デバッグ効率上がります。

ヘッダとして
<assert.h>
をインクルードしてください。

動作確認ができたら
NDEBUGマクロを定義すると
assertは空になり、無害となります。

pon

Re:初心者です。

#22

投稿記事 by pon » 15年前

すべてmain関数に入れない方法が分からないうえに、自分のレベルだとすべてmain関数に入れて問題が発生しないので・・・すいません。

あと110行目の何がいけないのか教えていただけませんか?
配列の10番目までないものが存在するということでしょうか

GannRock

Re:初心者です。

#23

投稿記事 by GannRock » 15年前

110行目に問題はありません。

106行目の
for(b=a+1;b<e;a++)
が原因で
110行目実行時に
とんでもない場所をアクセスするということです。

106行目を修正する必要があります。

>すべてmain関数に入れない方法が分からないうえに

かなり無謀だと思います。
「急がば回れ」と言うこともあります。

関数を作ったり
コメントをいれたり
assert()を入れたり

これらは、時間もかかるし、
一見無駄な様に思えます。

確かに「大天才」であれば不要かも知れません。

私も含め、凡人は必ず過ちを犯すので
予防線を張っておくのです。

そうしないと、この様にデバックで大騒ぎするのです。

box

Re:初心者です。

#24

投稿記事 by box » 15年前

>for(b=a+1;b<e;a++)

bの初期値をa+1とします。
bがeより小さい間、何かの処理を繰り返します。
何かの処理が終わって、繰り返しをする前に、「a」をインクリメントします。→本当に正しいですか?

という、ご指摘が寄せられているのです。
画像

GannRock

Re:初心者です。

#25

投稿記事 by GannRock » 15年前

106行目
for(b=a+1;b<e;a++)


ほぼ確実に

for(b=a+1;b<e;b++)

の誤りです。

修正前のループでは
bは一切変化せずにaがどんどん増加します。
つまり
b < eは成立せずに無限ループとなってしまいます。
一方でaはどんどん増加するので
いつかはaが6000以上になります。

そのタイミングで
110行目の
if(answer[a][c] != answer[c])
を実行すると

answer[a][c]はchar answer[6000][10];
の外をアクセスしています。

どうなるか保証はありません。

たいちう

Re:初心者です。

#26

投稿記事 by たいちう » 15年前

最後にUpされているプログラムをデバッグしてみましたが、
完成はそれほど先の事ではないですよ。
細かい点を3箇所ほど直せば、重複ありでなら表示ができます。
まず、ここまでやってしまいましょう。

その後、重複を数えないようにするために一工夫したら完成です。

更にその後で元気があるならば、プログラムを改善しましょう。

pon

Re:初心者です。

#27

投稿記事 by pon » 15年前

コンパイルもでき、実行もできたのですが、結果が負になってしまいました…

fatens

Re:初心者です。

#28

投稿記事 by fatens » 15年前

>コンパイルもでき、実行もできたのですが、結果が負になってしまいました…

私も関数に分けて、コメントも入れた方が良いと思います。
そうすればおかしな結果になったときに修正しやすいです。

一応作ってみたものを添付するので、よければ見て下さい。
ponさんが文字列で作っているので、私は数値で作ってみたのですが、
これはこれで、条件演算子が酷いことになってます。
たぶん動くと思うんですが、間違ってたら誰か指摘して下さい。

if(k==2)
{
for(a=0;a<n;a++)
{
for(b=0;b<n;b++)
{
if(a != b)
{
sprintf(answer[e],"%d%d",card[a],card);
sprintf(answer[e+1],"%d%d",card,card[a]);
e=e+2;
}
}
}
}

ところでこのループですが、例えば n = 4 の場合を考えると、
(a, b) = (0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3)
(2, 0), (2, 1), (2, 3), (3, 0), (3, 1), (3, 2)
のようになるので、二度目のsprintf 関数の呼び出しは不要で、eも一つ増やすだけで良いと思います。
同様のことが k == 3, k == 4 の場合にも言えるので、それも削れるかと。

たいちう

Re:初心者です。

#29

投稿記事 by たいちう » 15年前

> これはこれで、条件演算子が酷いことになってます。
> たぶん動くと思うんですが、間違ってたら誰か指摘して下さい。

動かして試したわけではありませんが、このように書くことができます。

data = cards[a];
data = data * (cards >= 10 ? 100 : 10) + card;
data = data * (cards[c] >= 10 ? 100 : 10) + card[c];
data = data * (cards[d] >= 10 ? 100 : 10) + card[d];

たいちう

Re:初心者です。

#30

投稿記事 by たいちう » 15年前

> コンパイルもでき、実行もできたのですが、
> 結果が負になってしまいました…

デバッグの仕方を勉強しましょう。
デバッガの使い方を覚えるか、要所要所にprintfで値を表示してみるかです。
後者について簡単に説明します。

ponさんは結果しか気にしていないようですが、
内部的に途中経過があって最終的に結果が表示されています。
途中経過はプログラマが想定した過程を通るはずですが、
最終結果が想定と違うならば、途中経過のどこかで、
意図していない事態になったわけです。

結果が負になったということですが、
結果に何が代入されているか、各段階でprintfで確認する事で、
想定と違う事態がいつ発生したかを突き止めます。
これがデバッグです。

今回はkosuuの初期化が問題だと思いますが、
今説明したprintfを使ったデバッグで、どのように気付くことが
できたかを考えてみてください。

fatens

Re:初心者です。

#31

投稿記事 by fatens » 15年前

>動かして試したわけではありませんが、このように書くことができます。
元の数を次の数の桁数におおじて左にシフトさせる感じですね。
私のコードよりはるかにわかりやすいです。
勉強になりました。

これを踏まえて修正したものを添付しておきます。
画像

pon

Re:初心者です。

#32

投稿記事 by pon » 15年前

>>fatensさん
そうですね。自分でループさせたのにそれを忘れていました。ご指摘ありがとうございます。

>>たいちうさん
kosuu=0;と入れるのを忘れているということですね。ご指摘ありがとうございます。

これでokと思ったのですが、kosuu関数が常に0になっているようです。
eの数は合っているのですが、何故kosuuが0になってしまうのでしょう。
御指摘通りいろいろprintfを入れたのですがよく分かりませんでした。

たいちう

Re:初心者です。

#33

投稿記事 by たいちう » 15年前

> 御指摘通りいろいろprintfを入れたのですが
> よく分かりませんでした。

適当に入れても仕方ないですよ。
kosuu++が呼ばれていないのが症状なので、
どうしてそうなるのかを突き止めるわけです。

で、少なくとも次のことを突き止める必要があったのです。

× : if(flag[a]=0)
○ : if(flag[a]==0)

pon

Re:初心者です。

#34

投稿記事 by pon » 15年前

あ、そうですね。ご指摘ありがとうございます。
今度は全てflagが0になってしまいました

たいちう

Re:初心者です。

#35

投稿記事 by たいちう » 15年前

kosuu = 0;
for(a=0;a<e;a++)
{
    flag1=1;         // 数字aを数える必要があることを表すフラグ
    for(b=0;b<a;b++) // 既に数えたかどうかを判定するため、b < aについて調べる
    {
        flag2 = 1;   // 数字a == 数字bを表すフラグ
        for(c=0;c<10;c++)
        {
            if(answer[a][c] != answer[c])
            {
                flag2=0;  // 数字a != 数字b
            }
        }
        if (flag2 == 1) // 既に数字bを数えているはずなので
            flag1 = 0;  // 数字aは数える必要がない
    }
    if(flag1==1)
    {
        kosuu++;
    }
}
printf("kosuu = %d\n", kosuu);

それと文字列の比較にはstrcmpを使った方が良いでしょう。
それとC++ならばこんなに簡単という例。色々手抜きですが。
重複除去以外はCでも同じように書けます。
#include <iostream>
#include <set>

using namespace std;

int used;
set<int> numbers;
int card[10];

void sub(int n, int k, int work) {
    if (k == 0) {
        numbers.insert(work);
    } else {
        for (int i = 0; i < n; i++) {
            int bit = 1 << i;
            if ((used & bit) == 0) {
                used |= bit;
                if (card < 10)
                    sub(n, k - 1, work * 10 + card);
                else
                    sub(n, k - 1, work * 100 + card);
                used &= ~bit;
            }
        }
    }
}

int main() {
    // 入力例2
    int n = 6;
    int k = 3;
    card[0] = 72;
    card[1] = 2;
    card[2] = 12;
    card[3] = 7;
    card[4] = 2;
    card[5] = 1;

    sub(n, k, 0);
    cout << static_cast<int>(numbers.size()) << endl;

    return 0;
}

pon

Re:初心者です。

#36

投稿記事 by pon » 15年前

>>たいちうさん
やっぱりだめです
この方法と自分の方法は同じではありませんか?

たいちう

Re:初心者です。

#37

投稿記事 by たいちう » 15年前

> やっぱりだめです
> この方法と自分の方法は同じではありませんか?

違いますよ。
試したソースコードを添付してください。

pon

Re:初心者です。

#38

投稿記事 by pon » 15年前

すいません。int flag2の後に;を入れ忘れていただけで、入れたら出来ました。
でも、自分の方法と何が違うのでしょうか
前を調べるかと後ろを調べるのとは同じではありませんか?

たいちう

Re:初心者です。

#39

投稿記事 by たいちう » 15年前

for(a=0;a<e;a++)
{
    flag[a]=0;
    for(b=a+1;b<e;b++)
    {
        for(c=0;c<10;c++)
        {
            if(answer[a][c] != answer[c])
            {
                flag[a]=1;
            }
        }
    }
    if(flag[a]==0)
    {
        kosuu++;
        printf("%d\n",flag[a]);
    }
}

ponさんの条件では、aより後の全てのbと比較して、
1つでも(数字a != 数字b)ならば数えない、としています。
結局この条件を満たすのは最後のデータ(aより後のbが存在しないから)のみとなり、
kosuuが1になってしまいます。

たいちう

Re:初心者です。

#40

投稿記事 by たいちう » 15年前

一組のトランプをシャッフルして10枚ほど取り、
何種類の数字が現れたか数える方法を考えると良いでしょう。
自分の手で数える場合にどのようにやるかをプログラムにするだけです。

pon

Re:初心者です。

#41

投稿記事 by pon » 15年前

そうですね。アルゴリズムを自分で全く理解していませんでした。

みなさん長くなりましたがありがとうございました

閉鎖

“C言語何でも質問掲示板” へ戻る