初心者です。
初心者です。
この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ログを見て、自分で分かる限り書き変えたのですが、これ以上分からないので、よろしくお願いします。
自分がやりたいこととしては、くっつけてできるすべての数を配列にいれて、配列をあとで昇順に並べて同じのを省いて個数を数えるということをしたいのですが
まだ、配列を昇順に並べて~は実装していません。
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:初心者です。
まず、問題のリンクが参照出来ませんのでちゃんとリンクをお願いします。
問題文が分からないで何をしたいか分かりません。
それと、ぱっと見た限りは、文字と文字列の区別が出来ていません。どのぐらいC言語で勉強したか教えてください。現状、この問題を解くにはC言語の経験不足としか思えません。
下記のサイトの14章の文字列を扱う方法を読んでください。
http://homepage3.nifty.com/mmgames/c_guide/
14章の練習問題は簡単に解けますか?
問題文が分からないで何をしたいか分かりません。
それと、ぱっと見た限りは、文字と文字列の区別が出来ていません。どのぐらいC言語で勉強したか教えてください。現状、この問題を解くにはC言語の経験不足としか思えません。
下記のサイトの14章の文字列を扱う方法を読んでください。
http://homepage3.nifty.com/mmgames/c_guide/
14章の練習問題は簡単に解けますか?

Re:初心者です。
http://www.ioi-jp.org/joi/2009/2010-yo- ... yo-t4.html
すいません。コレです
strcatではなく、sprintfを使えば良いのでしょうか?
sprintfを使えばあらかじめk*k!個の予備を作る必要がなさそうですが
すいません。コレです
strcatではなく、sprintfを使えば良いのでしょうか?
sprintfを使えばあらかじめk*k!個の予備を作る必要がなさそうですが
Re:初心者です。
間違っているところ。
(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で同じかどうか比較してください。
アルゴリズムとしては、自分より後に同じ数値が出てこない数値をカウントすれば個数を求めることが出来ると思います。
(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:初心者です。
> forの間違いとは何ですか?
"2010/03/23(火) 13:47"のリンク先のプログラムはコンパイルが通りませんでしたので、
そのことでしょう。
> このプログラムにおけるcharと intの違いは何ですか?
元のプログラムでは、1つのカードをchar型の変数で表すつもりなのか、
char型の配列、つまり文字列で表すつもりなのか、不明でした。
(どっちとみなしても間違いがありました)
そのため文字列で扱うよりも整数で扱った方が楽だよ、という意味でした。
> 一応コンパイルできるようになりましたが、かなり遅いです。
> どうすれば効率の良いプログラムになるでしょうか
効率の話の前に確認ですが、コンパイルが通っただけですか?
正しい答えが出せるようになったのですか?
原則として、効率の事を考える前に正しく動くプログラムを作る必要があります。
"2010/03/23(火) 13:47"のリンク先のプログラムはコンパイルが通りませんでしたので、
そのことでしょう。
> このプログラムにおけるcharと intの違いは何ですか?
元のプログラムでは、1つのカードをchar型の変数で表すつもりなのか、
char型の配列、つまり文字列で表すつもりなのか、不明でした。
(どっちとみなしても間違いがありました)
そのため文字列で扱うよりも整数で扱った方が楽だよ、という意味でした。
> 一応コンパイルできるようになりましたが、かなり遅いです。
> どうすれば効率の良いプログラムになるでしょうか
効率の話の前に確認ですが、コンパイルが通っただけですか?
正しい答えが出せるようになったのですか?
原則として、効率の事を考える前に正しく動くプログラムを作る必要があります。
Re:初心者です。
最新の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は空になり、無害となります。
まず、基本的な問題としてコードが醜いです。
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:初心者です。
110行目に問題はありません。
106行目の
for(b=a+1;b<e;a++)
が原因で
110行目実行時に
とんでもない場所をアクセスするということです。
106行目を修正する必要があります。
>すべてmain関数に入れない方法が分からないうえに
かなり無謀だと思います。
「急がば回れ」と言うこともあります。
関数を作ったり
コメントをいれたり
assert()を入れたり
これらは、時間もかかるし、
一見無駄な様に思えます。
確かに「大天才」であれば不要かも知れません。
私も含め、凡人は必ず過ちを犯すので
予防線を張っておくのです。
そうしないと、この様にデバックで大騒ぎするのです。
106行目の
for(b=a+1;b<e;a++)
が原因で
110行目実行時に
とんでもない場所をアクセスするということです。
106行目を修正する必要があります。
>すべてmain関数に入れない方法が分からないうえに
かなり無謀だと思います。
「急がば回れ」と言うこともあります。
関数を作ったり
コメントをいれたり
assert()を入れたり
これらは、時間もかかるし、
一見無駄な様に思えます。
確かに「大天才」であれば不要かも知れません。
私も含め、凡人は必ず過ちを犯すので
予防線を張っておくのです。
そうしないと、この様にデバックで大騒ぎするのです。
Re:初心者です。
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];
の外をアクセスしています。
どうなるか保証はありません。
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:初心者です。
>コンパイルもでき、実行もできたのですが、結果が負になってしまいました…
私も関数に分けて、コメントも入れた方が良いと思います。
そうすればおかしな結果になったときに修正しやすいです。
一応作ってみたものを添付するので、よければ見て下さい。
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 の場合にも言えるので、それも削れるかと。
私も関数に分けて、コメントも入れた方が良いと思います。
そうすればおかしな結果になったときに修正しやすいです。
一応作ってみたものを添付するので、よければ見て下さい。
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:初心者です。
> コンパイルもでき、実行もできたのですが、
> 結果が負になってしまいました…
デバッグの仕方を勉強しましょう。
デバッガの使い方を覚えるか、要所要所にprintfで値を表示してみるかです。
後者について簡単に説明します。
ponさんは結果しか気にしていないようですが、
内部的に途中経過があって最終的に結果が表示されています。
途中経過はプログラマが想定した過程を通るはずですが、
最終結果が想定と違うならば、途中経過のどこかで、
意図していない事態になったわけです。
結果が負になったということですが、
結果に何が代入されているか、各段階でprintfで確認する事で、
想定と違う事態がいつ発生したかを突き止めます。
これがデバッグです。
今回はkosuuの初期化が問題だと思いますが、
今説明したprintfを使ったデバッグで、どのように気付くことが
できたかを考えてみてください。
> 結果が負になってしまいました…
デバッグの仕方を勉強しましょう。
デバッガの使い方を覚えるか、要所要所にprintfで値を表示してみるかです。
後者について簡単に説明します。
ponさんは結果しか気にしていないようですが、
内部的に途中経過があって最終的に結果が表示されています。
途中経過はプログラマが想定した過程を通るはずですが、
最終結果が想定と違うならば、途中経過のどこかで、
意図していない事態になったわけです。
結果が負になったということですが、
結果に何が代入されているか、各段階でprintfで確認する事で、
想定と違う事態がいつ発生したかを突き止めます。
これがデバッグです。
今回はkosuuの初期化が問題だと思いますが、
今説明したprintfを使ったデバッグで、どのように気付くことが
できたかを考えてみてください。
Re:初心者です。
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:初心者です。
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になってしまいます。