C言語関係掲示板

過去ログ

No.547.系列の削除と挿入

[戻る] [ホームページ]
No.4732

系列の削除と挿入
投稿者---hiro(2003/01/28 19:54:59)


すいません。前回の説明では不足でした。
僕が作ろうとしているのは符号関係のプログラムなのですが、
もう一度初めから説明します。
まず、A=0110100001とします。
このAに対して、
1、 まず先頭の0を削除します。そうすると、110100001となります。
2、 次にこの110100001に0と1を挿入をします。すなわち、
0110100001   1110100001
1010100001   1110100001
1100100001   1110100001
1100100001   1101100001
1101000001   1101100001
1101000001   1101010001
1101000001   1101001001
1101000001   1101000101
1101000001   1101000011
1101000010   1101000011

という、系列ができます。
3、さらに今度は先頭から2番目を削除、すなわち010100001とし、
2をくりかえします。
この削除と挿入を先頭から最後まで繰り返すと出来上がる系列は20×10=200個
となります。
最後に元にあったAと出来上がった200個の系列を次の式に当てはめて比較します。
A=0110100001=R1R2R3…R10と置いたとき、
S=遙蕁滷劭蕁mod X)   (ただし、iは1〜n)
ここでnは系列の数、すなわちn=10です。
Aをこの式に当てはめると
S=1×0+2×1+3×1+4×0+5×1+6×0+7×0+8×0+9×0+10×1
 =20(mod X)
となります。ここで元にあったAのSは0でなければならないという条件があるので
X=20とおくことによってS=0となります。
さらに200個の系列を上記の式に当てはめ、次の条件に合うものの個数をカウントします。
1、 S=0でないもの
2、 0<S≦n かつ RS=1でないもの
3、 X−n≦S<n かつ RS=0でないもの
今は例としてn=10、すなわち系列を10個としているのですが、
最終的にn=100〜1000ぐらいにしてプログラムを作る場合はどのようにすればよいのか教えてください。


No.4754

Re:系列の削除と挿入
投稿者---カンナ(2003/01/28 23:00:55)
http://hana.sakura.ne.jp/~elfin/k/


 最適化等を一切考えず素直に作ったら以下のようになりました。
 条件を誤解しているかもしれません。私の解釈はanalyzeの中ごろにある
printfのとおりです。間違っていたら御指摘ください。
 なお掲載に当たって行数を節約するために引数チェックは行っていません。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* 途中経過を表示するか? */
int g_verbose = 0;	
    
/* 結果格納領域 */
typedef struct _result{
    int count[3];
}result_t;

/* プロトタイプ */
result_t analyze(const char* original);
int get_S(const char* sequence);
int condition1(int S);
int condition2(const char* sequence, int S, int n);
int condition3(const char* sequence, int S, int n, int X);

/* main */
int main(int argc, char* argv[]){
    result_t result = analyze(argv[1]);

    printf("条件1:%d\n条件2:%d\n条件3:%d\n", 
        result.count[0], result.count[1], result.count[2]);

    return 0;
}

/* 解析 */
result_t analyze(const char* original){
    /* 結果格納領域 */
    result_t result = { {0, 0, 0} };

    /* 作業領域 */
    char*  work_area;

    /* ループ変数等 */
    size_t ix_delete, ix_insert, ix_from, ix_to;
    int ch;

    /* 解析用変数 */    
    size_t n;
    int S;
    int X;

    /* 途中経過表示用連番 */
    int no = 0;

    /* 剰余係数の算出 */
    X = get_S(original);
    if ( g_verbose ) printf("X=%d\n", X);
    
    if ( X == 0 ){
        printf("Xが0になるので解析できません。\n");
        return result;
    }

    /* 長さの取得と作業領域の初期化 */
    n = strlen(original);
    work_area = (char*)malloc(sizeof(char)*(n+1));
    work_area[n] = '\0';

    if ( g_verbose ){
        printf("条件1:S!=0\n");
        printf("条件2:0       <  S <= n(%3d) かつ RS=0\n", n);
        printf("条件3:X-n(%3d)<= S <  n(%3d) かつ RS=1\n", X-n, n);
    }

    /* 先頭から順に削除する */
    for ( ix_delete = 0; ix_delete < n; ++ix_delete ){
        /* 先頭から順に挿入する */
        for ( ix_insert = 0; ix_insert < n; ++ix_insert){
            for ( ch = '0'; ch <= '1'; ++ch ){
                /* 系列の作成 */
                ix_from = 0;
                for ( ix_to = 0; ix_to < n; ++ix_to ){
                    if ( ix_from == ix_delete ) ++ix_from;
                    if ( ix_to == ix_insert ) work_area[ix_to] = ch;
                    else work_area[ix_to] = original[ix_from++];
                }
    
                if ( g_verbose ){
                    ++no; 
                    printf("%05d:%s", no, work_area);
                }
    
                /* 条件成立判定 */
                S = get_S(work_area) % X;
                if ( g_verbose ) printf(" S=%03d RS=%c", S, ( (0 < S && S <= (int)n) ? work_area[S-1] : '-'));
                if ( condition1(S)                  ) ++result.count[0];
                if ( condition2(work_area, S, n)    ) ++result.count[1];
                if ( condition3(work_area, S, n, X) ) ++result.count[2];
                if ( g_verbose ) printf("\n");
            }
        }
    }

    free(work_area);

    return result;
}

/* 系列の重みつきビット合計 */
int get_S(const char* sequence){
    int S = 0;
    int i;
    for ( i = 1; sequence[i-1] != '\0'; ++i )
        if ( sequence[i-1] == '1' ) S += i;

    return S;
}

/* S=0でないもの */
int condition1(int S){
    if ( S != 0 ){
        if ( g_verbose ) printf(" Y");
        return 1;
    }else{
        if ( g_verbose ) printf(" N");
        return 0;
    }
}

/* 0<S≦n かつ RS=1でないもの */
int condition2(const char* sequence, int S, int n){
    if ( 0 < S && S <= n && sequence[S-1] != '1' ){
        if ( g_verbose ) printf(" Y");
        return 1;
    }else{
        if ( g_verbose ) printf(" N");
        return 0;
    }
}

/* X−n≦S<n かつ RS=0でないもの */
int condition3(const char* sequence, int S, int n, int X){
    if ( X - n <= S && S < n && 0 < S && sequence[S-1] != '0' ){
        if ( g_verbose ) printf(" Y");
        return 1;
    }else{
        if ( g_verbose ) printf(" N");
        return 0;
    }
}


No.4829

Re:系列の削除と挿入
投稿者---hiro(2003/01/30 14:53:28)


かんなさん、助かりました!
自分でやってはいるもののなかなかうまくいかなかったので。
ありがとうございます。