表現上の等価性に対する再帰的な解決策
この場合、配列の等価性 (以下を参照) をチェックする代わりに、文字列として表され、連結された数値が等しいことをチェックします。例えば：
[1,2,3,4,5] === [12,34,5] === [123,45]
アイデアは、表現の文字列を最終値として、空の文字列を初期値として、各配列を縮小/折り畳み、各整数を取得して文字列に変換し、それを文字列の最後に連結することです。結果。次に、等しいかどうかを比較する 2 つの文字列を見つけます。
私の解決策にはいくつかの問題があることに注意してください。
まず、文字列操作の境界チェックを行っていないため、次のコードはメモリ全体を楽しく踏みにじります。
また、結果の最後を追跡しません。つまり、各連結は結果文字列をたどる必要があり、効率的な方法ではありません。
指定された itoa 実装の制限は、最大の負の整数に対して正しく機能しないことです。
ただし、一般的な考え方は同じままです。素敵なプログラミング言語では、次のように書くことができます:
(eq?
(reduce concat "" (map tostr [1,2,3,4,5] ))
(reduce concat "" (map tostr [1,2,3,4,5] )))
または同等のもの; しかし、これは C であるため、難しい方法で行う必要があります。
#include <assert.h>
#include <string.h>
#define SAME 0
#define DIFFER 1
void reverse(char s[]);
void itoa(int n, char s[]);
void reduce_to_string(char *result, int values[], int values_len){
char tmpstr[256] = "";
if( values_len == 0 ){ return; }
// convert the first number to a string, writing the representation to tmpstr
itoa(values[0], tmpstr);
// concatenate the first number with the accumulated string
result = strcat(result, tmpstr);
// recur with a smaller array.
return reduce_to_string(result, &values[1], (values_len-1));
}
int compare_representation(int a[], int a_len, int b[], int b_len){
char a_as_string[512] = "";
char b_as_string[512] = "";
reduce_to_string(a_as_string, a, a_len);
reduce_to_string(b_as_string, b, b_len);
if( 0 == strcmp(a_as_string, b_as_string) ){ return SAME;}
return DIFFER;
}
int main(void){
int b[] = {6,7,8,9};
int b_len = 4;
int c[] = {1,2,3,4,5};
int c_len = 5;
int d[] = {67, 89};
int d_len = 2;
assert(SAME == compare_representation(b,b_len,d,d_len));
assert(DIFFER == compare_representation(b,b_len,c,c_len));
return 0;
}
/*
* The following are from K&R C, second edition.
*/
/* reverse: reverse string s in place. page 62 */
void reverse(char s[])
{
int i, j;
char c;
for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
/* itoa: convert n to characters in s. page 64*/
void itoa(int n, char s[])
{
int i, sign;
if ((sign = n) < 0) /* record sign */
n = -n; /* make n positive */
i = 0;
do { /* generate digits in reverse order */
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
reverse(s);
}
構文の説明:
C を初めて使用する場合&a[1]、配列 'a' の末尾に使用することは明確ではない場合があります。
(テールと言うときは、最初の要素を除くすべての要素を意味します。)
英語に分解すると&a[1]、「配列 'a' の 2 番目の値のアドレス」のようになります。なぜこれが機能するのですか？Cでは、配列は変数を格納するために使用されるメモリの先頭へのポインターにすぎないため、2番目の変数のアドレスを取得すると、本質的に要素が1つ少ない配列が得られます。配列が小さいことを考慮に入れるために、次の関数呼び出しに渡す前に、配列長変数 'a_len' も減らします。
再帰的解法と反復解法 (配列が等しい場合)
どちらcompare_*の関数も、2 つの整数配列を比較して、配列が同一であることを確認します。
#include <assert.h>
#define SAME 0
#define DIFFER 1
int compare_recursive(int a[], int a_len, int b[], int b_len){
if( a_len != b_len ){ return DIFFER; }
if( a_len == 0 && b_len == 0 ){ return SAME; }
if(a[0] == b[0]){
return compare_recursive(&a[1], (a_len-1), &b[1], (b_len-1) );
}else{
return DIFFER;
}
}
int compare_iterative(int a[], int a_len, int b[], int b_len){
int i;
if( a_len != b_len ){ return DIFFER; }
for(i = 0; i < a_len; i++){
if( a[i] != b[i] ){ return DIFFER; }
}
return SAME;
}
int main(void){
int a[] = {1,2,3,4,5};
int a_len = 5;
int b[] = {6,7,8,9};
int b_len = 4;
int c[] = {1,2,3,4,5};
int c_len = 5;
assert(DIFFER == compare_recursive(a,a_len,b,b_len));
assert(SAME == compare_recursive(a,a_len,c,c_len));
assert(DIFFER == compare_iterative(a,a_len,b,b_len));
assert(SAME == compare_iterative(a,a_len,c,c_len));
return 0;
}