一直線上に並んだ線の複数のセットが重ならない様に計算する効率的なアルゴリズムは
ありませんか。できればC言語のサンプルや、アルゴリズム名があれば幸いです。
例)
パターンA -- -- -- --
パターンB - - - - -
パターンC - - -
線では分かりにくいので、アルファベットに変えます。
パターンA AA■■■AA■■■AA■■■AA
パターンB B■■■■B■■■■B■■■■B
パターンC C■■■■■■■C■■■■■■■C
※■=空白
ABCを重ならない様にマージ
(マージ過程・ずらしながら確認)
AA■■■AA■■■AA■■■AA
■■■B■■■■B■■■■B■■■■B
■■■■■■C■■■■■■■C■■■■■■■C
●結果例 1つのパターン例
AA■B■■CAA■B■■AA■BC■AA■B■■■C
No.1ベストアンサー
- 回答日時:
64bit整数を使って比較処理を簡素化していますが、
アルゴリズム的には特に何も工夫していない、総当たりのコードです。
各パターンセットの最大長は64個までとなっています。
Visual C++ 2010でのみテスト済み。
すべての組み合わせを確認する場合は出力をファイルにリダイレクトしてください。
#include <stdio.h>
#include <conio.h>
void PrintBin64Inv(unsigned long long v)
{
int i;
for (i = 0; i < 64; i++)
{
putchar(v & (1LL << i) ? '1' : '0');
}
putchar('\n');
}
void main()
{
// 最下位ビットを左端に、最上位ビットを右端に逆表示する。
const unsigned long long ptnA = 0x18c63, ptnB = 0x8421, ptnC = 0x10101;
int shb = 0, shc = 0;
printf("PatternA = ");
PrintBin64Inv(ptnA);
printf("PatternB = ");
PrintBin64Inv(ptnB);
printf("PatternC = ");
PrintBin64Inv(ptnC);
for (shb = 0; shb < 32; shb++)
{
if ((ptnA & (ptnB << shb)) == 0)
{
for (shc = 0; shc < 32; shc++)
{
if (((ptnA | (ptnB << shb)) & (ptnC << shc)) == 0)
{
printf("ShiftAmountB = %d, ShiftAmountC = %d\n", shb, shc);
printf("PatternA = ");
PrintBin64Inv(ptnA);
printf("PatternB2 = ");
PrintBin64Inv(ptnB << shb);
printf("PatternC2 = ");
PrintBin64Inv(ptnC << shc);
continue;
}
}
}
}
puts("Press any key to exit...");
_getch();
}
回答ありがとうございます。
やはり総当りで見ていくしかないですかね。
ご提示のプログラムの通り、ビットで判定していく方法が簡単そうですので、参考にさせていただきます。
さらに、総当りで考えると、順列的にABC,ACB、BAC,BCA,CAB,CBAもありますので、全パターンを確認して、最適解を出す様にしたいと思います。
ありがとうございました。
No.2
- 回答日時:
>一直線上に並んだ線の複数のセットが重ならない様に計算する・・
難解だなぁ・・。
>パターンA AA■■■AA■■■AA■■■AA
>パターンB B■■■■B■■■■B■■■■B
>パターンC C■■■■■■■C■■■■■■■C
■ を半角1文字 / として、
パターンA AA/// 5文字の繰り返し
パターンB B//// 5文字の繰り返し
パターンC C/////// 8文字の繰り返し
5と5と8の最小公倍数40まで、「重ならない様に計算する」。
違っていたら、ここまで・・残念。
++++++++++++++++++++++++++++++++++++++++++++++++++++++
ボケ防止対策として・・考えてみました(「●結果例」を無視、失礼)。
・方法:「ずらしながら確認」
#include <stdio.h>
#include <string.h>
#define ALEN 5 // ■が半角2文字の場合8
#define BLEN 5 // ■が半角2文字の場合9
#define CLEN 8 // ■が半角2文字の場合15
#define K_LEN (ALEN*CLEN) // ■が半角2文字の場合(ALEN*BLEN*CLEN)
void main()
{
int i, A, C, iTop;
char cStrA[ 16 ] = "AA///"; // 〃 AA//////
char cStrB[ 16 ] = "B////"; // 〃 B////////
char cStrC[ 16 ] = "C///////"; // 〃 C//////////////
char cWrk1[ K_LEN + 1 ] = { '\0' }, cWrk2[ K_LEN + 1 ];
for( A = 0; A < ALEN; A++ ){ // パターンB の始まりを「ずらしながら確認」
if( 'A' == cStrA[ A ] ) continue;
iTop = 0;
for( i = 0; i < K_LEN; i++ ) cWrk1[ i ] = cStrA[ i % ALEN ];
for( i = A; i < K_LEN; i++ ){
if( '/' == cWrk1[ i ] ) cWrk1[ i ] = cStrB[ ( i - A ) % BLEN ];
else{ // 重なり判定
if( 'B' == cStrB[ ( i - A ) % BLEN ] ){
iTop = i; // A, B 重なった場所
cWrk1[ i ] = '*';
break;
}
}
}
if( iTop ) cWrk1[ iTop + 1 ] = '\0';
printf( "A+B %d %3d %s\n", A, iTop, cWrk1 );
for( i = 0; i < ALEN; i++ ){ // パターンC の始まりを「ずらしながら確認」
if( '/' != cWrk1[ i ] ) continue;
strcpy( cWrk2, cWrk1 );
iTop = 0;
for( C = i; C < K_LEN; C++ ){
if( '/' == cWrk2[ C ] ) cWrk2[ C ] = cStrC[ ( C - i ) % CLEN ];
else{ // ( A or B ), C 重なり判定
if( '*' == cWrk2[ C ] ) iTop = C;
if( 'C' == cStrC[ ( C - i ) % CLEN ] ){
if( 0 == iTop ) iTop = C;
cWrk2[ C ] = '*';
}
if( iTop ) break;
}
}
cWrk2[ iTop + 1 ] = '\0';
printf( "A+B+C %d %3d %s\n", i, iTop, cWrk2 );
}
printf( "\n" );
}
}
注:インデントに全角空白を用いています。コピペ後、タブに一括変換して下さい。
ご回答ありがとうございます。
何か使えそうな幾何アルゴリズムがあればと質問しましたが、ご提示いただいたプログラムを見ていると、やはり単純にずらしながら確認していくしかない気がしてきました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) pythonのmap、結果の利用は1度だけ? 5 2022/06/11 12:33
- Excel(エクセル) Formulaプロパティーを使ってセルに数式を組んだのですが簡潔にしたい。 3 2022/08/21 20:51
- タブレット リカバリ用のUSBメモリ。 6 2022/10/24 15:19
- Visual Basic(VBA) Excel VBAでAA(BBB) → BBB.AA に置換したい 2 2022/10/30 13:59
- お酒・アルコール 断酒団体AAについての質問です 今年に入ってからお酒をやめました 自助グループとして「断酒会」と「A 3 2023/05/22 11:39
- その他(ニュース・時事問題) ノーベル書の価値 3 2023/03/05 13:13
- Visual Basic(VBA) マクロを教えてください。 7 2023/06/01 19:47
- その他(ネットショッピング・通販・ECサイト) 骨伝導ヘッドセットで この二つは値段が違うだけでは同じですか? 1 2023/02/13 19:13
- 実用・教育 その著者まで亡くなられたのですか? 2 2022/07/30 17:55
- その他(家族・家庭) 幼い2人の子は、孤児になるのでしょうか?? 1 2022/07/31 15:01
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語で四則演算を使って10を作...
-
wsprintfの書式制御文字列につ...
-
C言語です このプログラミング...
-
10個出力で改行したいのですが...
-
TeraPadの設定方法
-
万年カレンダーのC言語プログラ...
-
困ってます!Cプログラミングに...
-
4の倍数を論理演算で表す。。
-
両替プログラムなど
-
C言語で四則演算を使って結果が...
-
printf で二進表示を行いたい。
-
2の累乗を計算するプログラム...
-
C言語についてです学籍番号、名...
-
カレンダーのプログラムについて
-
switch文とscanfについて
-
一番大きい奇数を表示する
-
printf( " %2d", p * q );
-
ホームページをC言語で作りたい...
-
空Enterの扱い方
-
C言語について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語について
-
printf で二進表示を行いたい。
-
cshの文字列操作(0埋め)
-
10個出力で改行したいのですが...
-
コンパイルエラーについて
-
テキストカーソル位置の取得
-
strcmp
-
unsigned int型について
-
c言語でAからZまでを表示する...
-
printf( " %2d", p * q );
-
コマンドラインに出力した文字...
-
printfの出力内の文字をdefine...
-
ホームページをC言語で作りたい...
-
コマンドプロンプトがすぐ消える
-
小数点切捨て表示
-
【C言語教えてください】sin波...
-
switch分のケースを範囲数?に...
-
二つの整数値の大小比較
-
4の倍数を論理演算で表す。。
-
defineで定数が置き換えられな...
おすすめ情報