総当たりプログラムでつまずいてます

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

総当たりプログラムでつまずいてます

#1

投稿記事 by のりを » 3年前

スタート文字列から終了文字列まで総当たりするプログラムを作成しています。
文字列は"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_"の64文字です。
最初にスタート文字列と終了文字列を10進数に変換し、ループ中に10進数から64進数に変換しようと考えていますが正しいでしょうか?

一応64⇔10進数変換までは書けてますが、望んでいる結果になりません。
自分が作成した関数ですと例えば「aaa」とすると10進数は当然0になります。
「aaa」で10進数に変換してから64進数に戻したときに「aaa」に戻ってほしいのですが、
この場合どのようにしたらいいのでしょうか?

コード:

void Convert_Str_10(char* s, char* e)
{
	int i[] = { 0 };
	int n = 0;
	int m = 0;
	int x = 0;
	int y = 0;
	int z = 0;

	char* start = s;
	char* end = e;

	const char* Characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_"; // 64 Characters

	z = 0;

	for (x = 0; x < strlen(start); x++)
	{
		for (y = 0; y < 64; y++)
		{
			if (start[x] == Characters[y])
			{
				i[z] = y;
				break;
			}
		}

		z++;
	}

	m = z;
	for (x = 0; x < m; x++)
	{
		n = 1;

		for (y = 0; y < z; y++)
		{
			n *= 64;
		}

		z -= 1;

		start_num += i[x] * n;
	}



	z = 0;

	for (x = 0; x < strlen(end); x++)
	{
		for (y = 0; y < 64; y++)
		{
			if (end[x] == Characters[y])
			{
				i[z] = y;
				break;
			}
		}

		z++;
	}

	m = z;

	for (x = 0; x < m; x++)
	{
		n = 1;

		for (y = 0; y < z; y++)
		{
			n *= 64;
		}

		z -= 1;

		end_num += i[x] * n;
	}
}

void Convert_10_64(int num, char** set64)
{
	const char* Characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_"; // 64 Characters

	int x = 0;
	int y = 0;
	int n = 0;

	char str[10] = { 0 };
	char set[10] = { 0 };

	while (1)
	{
		x = num / 64;

		if (num < 64)
		{
			y = num;
		}
		else
		{
			y = num % 64;
		}

		set[n] = Characters[y];
		num = x;
		n++;

		if (x == 0) break;
	}

	set[n] = '\0';
	x = 0;
	y = 0;
	n -= 1;

	while (x < n)
	{
		str[y] = set[n];
		y++;
		n--;
	}

	set[0] = '\0';
	strcpy_s(set, str);
	*set64 = set;
}

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 総当たりプログラムでつまずいてます

#2

投稿記事 by みけCAT » 3年前

「a」でも「aa」でも「aaa」でも「aaaaaaaaaaaaaaaaa」でも10進数にすると「0」になり、
10進数には桁数の情報は含まれません。
よって、桁数は別に保存し、64進数に変換する関数に渡すといいでしょう。

また、Convert_10_64関数の中に

コード:

	*set64 = set;
という行がありますが、これはこの関数から抜けた時点で消えるローカル変数へのポインタを代入しています。
関数から抜けた後は、このポインタは無効な場所を指しているので、デリファレンスしてはいけません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

のりを

Re: 総当たりプログラムでつまずいてます

#3

投稿記事 by のりを » 3年前

回答ありがとうございます。

スタートが「bbb(10進数だと266304)」、終了が「ccc(10進数だと532608)」だとすると

コード:

Convert_Str_10("bbb", "ccc");
while(start_num <= end_num) //266304 != 532680
{
Convert_10_64(start_num, &set64);
start_num++;
}
このようになると思うのですが、
スタートが「aaa(10進数だと0)」、終了が「baa(10進数だと262144)」以降だとすると、
Convert_10_64(start_num, &set64,strlen("aaa"));
このようにして文字数を渡して、0から262143までは64進数変換後の文字数に応じて先頭に「a」と追加するということでしょうか?
そうなると、無駄(というと語弊がありますが)な処理をしていると思うのですが、どのように対処するべきでしょうか?
みけCAT さんが書きました:
3年前
また、Convert_10_64関数の中に

コード:

	*set64 = set;
という行がありますが、これはこの関数から抜けた時点で消えるローカル変数へのポインタを代入しています。
関数から抜けた後は、このポインタは無効な場所を指しているので、デリファレンスしてはいけません。
char set64[]をグローバル変数にして
wsprintf(set64,"%s",set);
とした場合は問題ないでしょうか?

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 総当たりプログラムでつまずいてます

#4

投稿記事 by みけCAT » 3年前

のりを さんが書きました:
3年前
スタートが「aaa(10進数だと0)」、終了が「baa(10進数だと262144)」以降だとすると、
Convert_10_64(start_num, &set64,strlen("aaa"));
このようにして文字数を渡して、0から262143までは64進数変換後の文字数に応じて先頭に「a」と追加するということでしょうか?
そうなると、無駄(というと語弊がありますが)な処理をしていると思うのですが、どのように対処するべきでしょうか?
まず、毎回strlenを呼ぶのは無駄(運が良ければ最適化してくれるかもしれませんが、無駄な可能性)ですね。
ループ前に長さを1回取得し、それを使うといいでしょう。

コード:

const char* start = "aaa", *end = "ccc";
int len = strlen(start);
Convert_Str_10(start, end);
while(start_num <= end_num) //266304 != 532680
{
    Convert_10_64(start_num, &set64, len);
    start_num++;
}
また、10進数から64進数の変換処理では、
現在「xが0になるまで」となっている場所を、「xが0になるか、指定の桁数に到達するまで」とする方法があります。
しかし、これだと0に対する無駄な割り算が発生してしまいます。
「先頭にaを追加する」という処理の方が無駄が少ないでしょう。
のりを さんが書きました:
3年前
char set64[]をグローバル変数にして
wsprintf(set64,"%s",set);
とした場合は問題ないでしょうか?
wsprintfを使うと無駄にWindowsに依存する上、
UNICODEマクロが定義されていると文字列の型が合わなくなってしまうので、よくないですね。
今回の場合、char set64[]をグローバルの十分な要素数の配列とし、

コード:

strcpy(set64, set);
を使うといいでしょう。
もしくは、setを経由せずstrから直接strcpyをしてもいいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

のりを

Re: 総当たりプログラムでつまずいてます

#5

投稿記事 by のりを » 3年前

「先頭にaを追加」というのはこういうことでしょうか?

コード:

void Convert_10_64(int num, int len)
{
	const char* Characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_"; // 64 Characters

	int x = 0;
	int y = 0;
	int n = 0;

	char str[256] = { 0 };
	char set[256] = { 0 };
	*set64 = NULL;

	while (1)
	{
		x = num / 64;

		if (num < 64)
		{
			y = num;
		}
		else
		{
			y = num % 64;
		}

		set[n] = Characters[y];
		num = x;
		n++;

		if (x == 0) break;
	}

	while (strlen(set) <= len)
	{
		set[n] = 'a';
		n++;
	}

	set[n] = '\0';
	x = 0;
	y = 0;
	n -= 1;

	while (x < n)
	{
		str[y] = set[n];
		y++;
		n--;
	}

	strcpy_s(set64, 256, str);
}
start = "aaa"
end = "aab"
の実行結果がこちらです

コード:

1.aaa
2.aaa
3.aaa
4.aaa
5.aaa
6.aaa
7.aaa
8.aaa
9.aaa
10.aaa
11.aaa
12.aaa
13.aaa
14.aaa
15.aaa
16.aaa
17.aaa
18.aaa
19.aaa
20.aaa
21.aaa
22.aaa
23.aaa
24.aaa
25.aaa
26.aaa
27.aaa
28.aaa
29.aaa
30.aaa
31.aaa
32.aaa
33.aaa
34.aaa
35.aaa
36.aaa
37.aaa
38.aaa
39.aaa
40.aaa
41.aaa
42.aaa
43.aaa
44.aaa
45.aaa
46.aaa
47.aaa
48.aaa
49.aaa
50.aaa
51.aaa
52.aaa
53.aaa
54.aaa
55.aaa
56.aaa
57.aaa
58.aaa
59.aaa
60.aaa
61.aaa
62.aaa
63.aaa
64.aaa
65.aab
本来であれば
1.aaa
2.aab
となるように処理したいのですが。。。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 総当たりプログラムでつまずいてます

#6

投稿記事 by みけCAT » 3年前

Convert_Str_10関数が間違ってますね。
まず、配列iは1要素しか無いのに、2要素目以降に書き込んでいるため、範囲外へのアクセスとなり危険です。
十分な要素数を確保してください。
次に、n *= 64;を1回ずつ余計に実行しているため、値が64倍になっています。
該当部分のyのループを0ではなく1から始めるなどするといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

のりを

Re: 総当たりプログラムでつまずいてます

#7

投稿記事 by のりを » 3年前

無事に望んだ結果が出力されました。
お世話になりました。ありがとうございます。

コード:

void Convert_Str_10(char* s, char* e)
{
	int i[256] = { 0 };
	int n = 0;
	int m = 0;
	int x = 0;
	int y = 0;
	int z = 0;

	char* start = s;
	char* end = e;

	const char* Characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_"; // 64 Characters

	z = 0;

	for (x = 0; x < strlen(start); x++)
	{
		for (y = 0; y < 64; y++)
		{
			if (start[x] == Characters[y])
			{
				i[z] = y;
				break;
			}
		}

		z++;
	}

	m = z;
	for (x = 0; x < m; x++)
	{
		n = 1;

		for (y = 1; y < z; y++)
		{
			n *= 64;
		}

		z -= 1;

		start_num += i[x] * n;
	}



	z = 0;

	for (x = 0; x < strlen(end); x++)
	{
		for (y = 0; y < 64; y++)
		{
			if (end[x] == Characters[y])
			{
				i[z] = y;
				break;
			}
		}

		z++;
	}

	m = z;
	for (x = 0; x < m; x++)
	{
		n = 1;

		for (y = 1; y < z; y++)
		{
			n *= 64;
		}

		z -= 1;

		end_num += i[x] * n;
	}
}

void Convert_10_64(int num, int len)
{
	const char* Characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-_"; // 64 Characters

	int x = 0;
	int y = 0;
	int n = 0;

	char str[256] = { 0 };
	char set[256] = { 0 };
	*set64 = NULL;

	while (1)
	{
		x = num / 64;

		y = num % 64;

		set[n] = Characters[y];
		num = x;
		n++;

		if (x == 0) break;
	}

	while (strlen(set) < len)
	{
		set[n] = 'a';
		n++;
	}

	set[n] = '\0';
	x = 0;
	y = 0;
	n -= 1;

	while (x <= n)
	{
		str[y] = set[n];
		y++;
		n--;
	}

	str[y] = '\0';

	strcpy_s(set64, 256, str);
}

返信

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