0

前提
ベクトル(v = (v1, v2, ...vn)^T))が与えられた時にノルム(√(v^(T)v))を求めるアルゴリズムを考えて、c言語で実装しようとしています。

実現したいこと
①擬似コードで文章になっている部分をどのように記号で表せるのか知りたい
②擬似コードのアルゴリズムを実行するためには、どのように参考記事のプログラムを変更するべきか知りたい

ベクトルが与えられた時にノルムを求める、実装したいアルゴリズムの擬似コード

norm <- 0
next_address <- v
while next_address != NULL do
    current_cell <- *(next_address)
    norm <- (ベクトルの要素を2乗したものを足していくと考えられるが、擬似コードでどのようにかいたらいいかわからない)
    next_address <- (現在のセルのポインタが指すインデックスだと考えられるが、似コードでどのようにかいたらいいかわからない)
return sqrt(norm)

参考記事のノルムを計算するプログラム

#include <stdio.h>
#include <math.h>

/* ---------------------------------------------
  ベクトルの長さを求める
  引数1: vec ベクトル
  引数4: n ベクトルの要素数
  戻り値 vecの長さ
 ---------------------------------------------*/
double norm(double *vec, int n)
{
    int i;
    double s = 0.0;

    for ( i = 0; i < n; i++ ) {
        s += vec[i] * vec[i];
    }

    return sqrt(s);
}

/* main */
int main(void)
{
    double vec[] = {1.0, 2.0, 3.0};
    int n = 3;

    /* ベクトルの長さを求める */
    printf("ベクトルの長さ: %f\n", norm(vec, n));

    return 0;
}

理解していること
10次元ベクトル(0,1,0,0,2,0,0,3,0,0)の時、以下のように書けることは理解しています。

cell *v = a;
a.index = 2; a.value = 1; a.next = &b;
b.index = 5; b.value = 2; b.next = &c;
c.index = 8; c.value = 3; c.next = NULL;

また、ノルムの定義も以下のように考えています。
ノルム

2
  • これは、ベクトルが(C言語の配列ではなく)何かしらの連結リストとして与えられて、しかもその長さは任意長ということでしょうか? しかも10次元の場合の例を見るに、要素が0の場所は省略できるデータ構造のようです。想定なさっているベクトルの型(構造体の定義など)を追記して頂きたいです。
    – nekketsuuu
    2019年5月29日 3:53
  • @ nekketsuuu ご質問いただきましてありがとうございます。要素が0の場所は省略できるデータ構造の部分はその通りですが、「ベクトルの型」についてわからず、質問内容を正しく理解できず、お答えすることができず申し訳ございませんでした。
    – user32568
    2019年5月29日 7:10

1 件の回答 1

1

質問文に書かれた10次元の場合の例を見るに、入力として与えられるベクトルはC言語の配列ではなく、何かしらの連結リストとして表現することを想定なさっているようです。

C言語の配列と連結リストは異なるデータ構造であり、質問文に引用してあるプログラムをそのまま適用することはできません。たとえば連結リストは添え字から直接(定数時間で)データにアクセスすることができません。

今回実装したいアルゴリズムは本質的には「連結リストの全ての要素を確認しながら和を求めていく」ものです。

たとえば連結リストを表す構造体が次のものだったとします。

typedef struct cell {
    int index;           // 要素の行番号。
    int value;           // 要素の値。
    struct cell * next;  // リストの次の要素。無い場合はNULL。
} cell;

するとベクトルのノルムを求める疑似コードはこんな感じになります。

sum <- 0.0
while v != NULL do
    sum <- sum + v->value * v->value
    v <- v->next
return sqrt(sum)

連結リストの場合はこのように、「次の要素が存在するか調べながら、それぞれの要素を走査して足していく」形になります。

この疑似コードはほとんどC言語のコードそのものなので、このままC言語のプログラムとして書けるでしょう。

9
  • ご回答いただきましてありがとうございます。誠に恐縮ですが、「実装したいアルゴリズムの擬似コード」の変数をそのまま使用した場合、日本語で書いているnormとnext_addressへの代入は擬似コードでは表わせないのでしょうか。
    – user32568
    2019年5月29日 4:40
  • 1
    @NPP 表せますが、単に冗長なだけです。C言語のアロー演算子がどういう演算をしているのか確認してみてください。
    – nekketsuuu
    2019年5月29日 4:44
  • 一度冗長なものを理解してから明記いただいた擬似コードの理解が進むと思うのですが、可能であれば補足いただけますと大変助かります。
    – user32568
    2019年5月29日 4:50
  • @NPP アロー演算子とドット演算子の違いはご存知ですか?
    – nekketsuuu
    2019年5月29日 4:52
  • 2
    @NPP でしたら、その違いまでこの回答で説明すると長くなりすぎるので、違いについて質問する別質問を立てていただけませんでしょうか。両者の違いが分かっていれば、この回答に書いた疑似コードは質問文にあるものと同じことをしていると分かって頂けるはずです。この後C言語で実装することを考えると、ドット演算子を使って疑似コードを書くのはむしろ違和感があります。
    – nekketsuuu
    2019年5月29日 7:04

この質問に回答するには、ログインする必要があります。