ページ 1 / 1
初心者です。
Posted: 2010年3月22日(月) 23:35
by pon
この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ログを見て、自分で分かる限り書き変えたのですが、これ以上分からないので、よろしくお願いします。
自分がやりたいこととしては、くっつけてできるすべての数を配列にいれて、配列をあとで昇順に並べて同じのを省いて個数を数えるということをしたいのですが
まだ、配列を昇順に並べて~は実装していません。
Re:初心者です。
Posted: 2010年3月23日(火) 09:03
by softya
Re:初心者です。
Posted: 2010年3月23日(火) 10:12
by pon
すいません。マルチポストです、と明記するのを忘れていました…
Re:初心者です。
Posted: 2010年3月23日(火) 10:18
by softya
規約に書いてあると思いますが、こちらだけでなく知恵袋にも明記してください。
Re:初心者です。
Posted: 2010年3月23日(火) 11:16
by pon
知恵袋にマルチの件補足させていただきました
Re:初心者です。
Posted: 2010年3月23日(火) 11:33
by softya
まず、問題のリンクが参照出来ませんのでちゃんとリンクをお願いします。
問題文が分からないで何をしたいか分かりません。
それと、ぱっと見た限りは、文字と文字列の区別が出来ていません。どのぐらいC言語で勉強したか教えてください。現状、この問題を解くにはC言語の経験不足としか思えません。
下記のサイトの14章の文字列を扱う方法を読んでください。
http://homepage3.nifty.com/mmgames/c_guide/
14章の練習問題は簡単に解けますか?

Re:初心者です。
Posted: 2010年3月23日(火) 13:22
by pon
http://www.ioi-jp.org/joi/2009/2010-yo- ... yo-t4.html
すいません。コレです
strcatではなく、sprintfを使えば良いのでしょうか?
sprintfを使えばあらかじめk*k!個の予備を作る必要がなさそうですが
Re:初心者です。
Posted: 2010年3月23日(火) 13:47
by pon
Re:初心者です。
Posted: 2010年3月23日(火) 13:55
by たいちう
予選とはいえナントカオリンピックの問題なので初心者には難しいでしょう。
いきなり完璧なものを作ろうとしないで、まずは(n, k) = (4, 2)の場合専用の
プログラムを作ってはいかがでしょうか。
# 面白い問題を紹介してくれてありがとうございます。
Re:初心者です。
Posted: 2010年3月23日(火) 14:08
by たいちう
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]);
試してませんが、この類の間違いを直せば、正しい答えにずいぶん近づくと思います。
それとソートがデタラメ。
Re:初心者です。
Posted: 2010年3月23日(火) 14:34
by dic
VC++6 ではコンパイルできませんがC
Cだとできるのかな?・・・
Re:初心者です。
Posted: 2010年3月23日(火) 15:13
by softya
間違っているところ。
(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:初心者です。
Posted: 2010年3月23日(火) 15:38
by たいちう
入力部分以外のプログラムは作ったけど、
一枚のcardはcharやcharの配列ではなく、
1つの整数で表す方が簡単だと思うな。
行き詰ったら試してみてください。
Re:初心者です。
Posted: 2010年3月23日(火) 18:02
by pon
みなさんありがとうございます。
配列を先に並び替えることで配列の次の番号のと等しいかを比べていくだけで良いので手数が減るかなと思ったのと等しいのは数えず異なるのだけ数えるのが大変に思えたのですが
まず、配列の比較する方法は配列の1から比較する、で良いですか?
forの間違いとは何ですか?
配列の数が大きいのはあとでなおすよていですが、エラーを取り除こうと思っていたので。ご指摘ありがとうございます。
このプログラムにおけるcharとintの違いは何ですか?
Re:初心者です。
Posted: 2010年3月23日(火) 18:51
by pon
http://www1.axfc.net/uploader/Sc/so/95551.c
一応コンパイルできるようになりましたが、かなり遅いです。
どうすれば効率の良いプログラムになるでしょうか
Re:初心者です。
Posted: 2010年3月23日(火) 20:29
by たいちう
> forの間違いとは何ですか?
"2010/03/23(火) 13:47"のリンク先のプログラムはコンパイルが通りませんでしたので、
そのことでしょう。
> このプログラムにおけるcharと intの違いは何ですか?
元のプログラムでは、1つのカードをchar型の変数で表すつもりなのか、
char型の配列、つまり文字列で表すつもりなのか、不明でした。
(どっちとみなしても間違いがありました)
そのため文字列で扱うよりも整数で扱った方が楽だよ、という意味でした。
> 一応コンパイルできるようになりましたが、かなり遅いです。
> どうすれば効率の良いプログラムになるでしょうか
効率の話の前に確認ですが、コンパイルが通っただけですか?
正しい答えが出せるようになったのですか?
原則として、効率の事を考える前に正しく動くプログラムを作る必要があります。
Re:初心者です。
Posted: 2010年3月23日(火) 20:37
by pon
コンパイルは通りました。プログラムが全然終了しないので、もう少し効率の良いプログラムにしないといけないのかと。
Re:初心者です。
Posted: 2010年3月23日(火) 20:41
by たいちう
> コンパイルは通りました。プログラムが全然終了しないので、
> もう少し効率の良いプログラムにしないといけないのかと。
効率が悪いから終了しないのですか?
正しいプログラムではないから終了しないのではないですか?
どうやって確認します?
Re:初心者です。
Posted: 2010年3月23日(火) 20:52
by pon
確認の仕方は全く分かりませんが、最後のprintf~を除いても終了しませんでした
ループ関数が無限ループしているところはなさそうなのですが
Re:初心者です。
Posted: 2010年3月23日(火) 22:01
by たいちう
↓こんなのがありましたが。
for(b=a+1;b<e;a++)
Re:初心者です。
Posted: 2010年3月23日(火) 22:44
by GannRock
最新の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は空になり、無害となります。
Re:初心者です。
Posted: 2010年3月23日(火) 22:56
by pon
すべてmain関数に入れない方法が分からないうえに、自分のレベルだとすべてmain関数に入れて問題が発生しないので・・・すいません。
あと110行目の何がいけないのか教えていただけませんか?
配列の10番目までないものが存在するということでしょうか
Re:初心者です。
Posted: 2010年3月23日(火) 23:16
by GannRock
110行目に問題はありません。
106行目の
for(b=a+1;b<e;a++)
が原因で
110行目実行時に
とんでもない場所をアクセスするということです。
106行目を修正する必要があります。
>すべてmain関数に入れない方法が分からないうえに
かなり無謀だと思います。
「急がば回れ」と言うこともあります。
関数を作ったり
コメントをいれたり
assert()を入れたり
これらは、時間もかかるし、
一見無駄な様に思えます。
確かに「大天才」であれば不要かも知れません。
私も含め、凡人は必ず過ちを犯すので
予防線を張っておくのです。
そうしないと、この様にデバックで大騒ぎするのです。
Re:初心者です。
Posted: 2010年3月23日(火) 23:19
by box
>for(b=a+1;b<e;a++)
bの初期値をa+1とします。
bがeより小さい間、何かの処理を繰り返します。
何かの処理が終わって、繰り返しをする前に、「a」をインクリメントします。→本当に正しいですか?
という、ご指摘が寄せられているのです。

Re:初心者です。
Posted: 2010年3月24日(水) 07:56
by GannRock
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:初心者です。
Posted: 2010年3月24日(水) 09:07
by たいちう
最後にUpされているプログラムをデバッグしてみましたが、
完成はそれほど先の事ではないですよ。
細かい点を3箇所ほど直せば、重複ありでなら表示ができます。
まず、ここまでやってしまいましょう。
その後、重複を数えないようにするために一工夫したら完成です。
更にその後で元気があるならば、プログラムを改善しましょう。
Re:初心者です。
Posted: 2010年3月24日(水) 11:20
by pon
コンパイルもでき、実行もできたのですが、結果が負になってしまいました…
Re:初心者です。
Posted: 2010年3月24日(水) 11:48
by fatens
>コンパイルもでき、実行もできたのですが、結果が負になってしまいました…
私も関数に分けて、コメントも入れた方が良いと思います。
そうすればおかしな結果になったときに修正しやすいです。
一応作ってみたものを添付するので、よければ見て下さい。
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:初心者です。
Posted: 2010年3月24日(水) 13:12
by たいちう
> これはこれで、条件演算子が酷いことになってます。
> たぶん動くと思うんですが、間違ってたら誰か指摘して下さい。
動かして試したわけではありませんが、このように書くことができます。
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:初心者です。
Posted: 2010年3月24日(水) 13:35
by たいちう
> コンパイルもでき、実行もできたのですが、
> 結果が負になってしまいました…
デバッグの仕方を勉強しましょう。
デバッガの使い方を覚えるか、要所要所にprintfで値を表示してみるかです。
後者について簡単に説明します。
ponさんは結果しか気にしていないようですが、
内部的に途中経過があって最終的に結果が表示されています。
途中経過はプログラマが想定した過程を通るはずですが、
最終結果が想定と違うならば、途中経過のどこかで、
意図していない事態になったわけです。
結果が負になったということですが、
結果に何が代入されているか、各段階でprintfで確認する事で、
想定と違う事態がいつ発生したかを突き止めます。
これがデバッグです。
今回はkosuuの初期化が問題だと思いますが、
今説明したprintfを使ったデバッグで、どのように気付くことが
できたかを考えてみてください。
Re:初心者です。
Posted: 2010年3月24日(水) 13:42
by fatens
>動かして試したわけではありませんが、このように書くことができます。
元の数を次の数の桁数におおじて左にシフトさせる感じですね。
私のコードよりはるかにわかりやすいです。
勉強になりました。
これを踏まえて修正したものを添付しておきます。

Re:初心者です。
Posted: 2010年3月24日(水) 14:34
by pon
>>fatensさん
そうですね。自分でループさせたのにそれを忘れていました。ご指摘ありがとうございます。
>>たいちうさん
kosuu=0;と入れるのを忘れているということですね。ご指摘ありがとうございます。
これでokと思ったのですが、kosuu関数が常に0になっているようです。
eの数は合っているのですが、何故kosuuが0になってしまうのでしょう。
御指摘通りいろいろprintfを入れたのですがよく分かりませんでした。
Re:初心者です。
Posted: 2010年3月24日(水) 14:52
by たいちう
> 御指摘通りいろいろprintfを入れたのですが
> よく分かりませんでした。
適当に入れても仕方ないですよ。
kosuu++が呼ばれていないのが症状なので、
どうしてそうなるのかを突き止めるわけです。
で、少なくとも次のことを突き止める必要があったのです。
× : if(flag[a]=0)
○ : if(flag[a]==0)
Re:初心者です。
Posted: 2010年3月24日(水) 14:58
by pon
あ、そうですね。ご指摘ありがとうございます。
今度は全てflagが0になってしまいました
Re:初心者です。
Posted: 2010年3月24日(水) 15:17
by たいちう
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;
}
Re:初心者です。
Posted: 2010年3月24日(水) 16:07
by pon
>>たいちうさん
やっぱりだめです
この方法と自分の方法は同じではありませんか?
Re:初心者です。
Posted: 2010年3月24日(水) 16:25
by たいちう
> やっぱりだめです
> この方法と自分の方法は同じではありませんか?
違いますよ。
試したソースコードを添付してください。
Re:初心者です。
Posted: 2010年3月24日(水) 16:29
by pon
すいません。int flag2の後に;を入れ忘れていただけで、入れたら出来ました。
でも、自分の方法と何が違うのでしょうか
前を調べるかと後ろを調べるのとは同じではありませんか?
Re:初心者です。
Posted: 2010年3月24日(水) 16:41
by たいちう
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:初心者です。
Posted: 2010年3月24日(水) 16:44
by たいちう
一組のトランプをシャッフルして10枚ほど取り、
何種類の数字が現れたか数える方法を考えると良いでしょう。
自分の手で数える場合にどのようにやるかをプログラムにするだけです。
Re:初心者です。
Posted: 2010年3月24日(水) 17:02
by pon
そうですね。アルゴリズムを自分で全く理解していませんでした。
みなさん長くなりましたがありがとうございました