プログラミングのＣ言語について

質問

|1 1 1 1 1 |
|1 2 3 4 5 |
|1 3 6 10 15 |
|1 4 10 20 35 |
|1 5 15 35 70 |

n=5の時にこの形の行列を作るにはどのようにプログラムを組めばいいですか？

回答No.3

hanabutako

追記しますが、uint64_tだとn = 35くらいで溢れて正しい値を出さなくなるので、nをそれ以上の値にしたかったらGMP (http://gmplib.org/)などの桁あふれせずに大きな数値を使えるようにするライブラリーを使ったほうがよいです。GMPの他では、OpenSSLのbn (http://www.openssl.org/docs/crypto/bn.html)やlibgcryptのMPI (http://www.gnupg.org/documentation/manuals/gcrypt/MPI-library.html) などが有名でしょうか。
ちなみに、OpenSSLやlibgcryptで大きな数値の計算を正確に扱える機能を提供しているのはRSAなどの公開鍵暗号の実装に必要だからだと思います。

一応、n = 100などにしても動くようGMPを使って書きなおしてみました。また、前の実装だとn = 100の実行は現実的な時間に終わらないので、効率化しました。
#include <err.h>
#include <gmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char *argv[])
{
if (argc != 2) {
errx(-1, "%s <n>", argv[0]);
}
size_t n = strtoul(argv[1], NULL, 10);
size_t current_pos = 0;
mpz_t *previous, *current;
mpz_t buf[2][n];
for (size_t i = 0; i < 2; i++) {
for (size_t j = 0; j < n; j++) {
mpz_init(buf[i][j]);
}
}

for (size_t i = 0; i < n; i++) {
current_pos = 1 - current_pos;
current = buf[current_pos];
previous = buf[1 - current_pos];

printf("|");
for (size_t j = 0; j < n; j++) {
if (i == 0 || j == 0) {
mpz_set_ui(current[j], 1);
} else {
mpz_add(current[j], previous[j], current[j - 1]);
}
char* to_str = mpz_get_str(NULL, 10, current[j]);
printf("%s ", to_str);
free(to_str);
}
printf("|\n");
}

for (size_t i = 0; i < 2; i++) {
for (size_t j = 0; j < n; j++) {
mpz_clear(buf[i][j]);
}
}

return 0;
}

ちなみに、BNを使うとこんな感じです。
#include <err.h>
#include <openssl/bn.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char *argv[])
{
if (argc != 2) {
errx(-1, "%s <n>", argv[0]);
}
size_t n = strtoul(argv[1], NULL, 10);
size_t current_pos = 0;
BIGNUM *previous, *current;
BIGNUM buf[2][n];
for (size_t i = 0; i < 2; i++) {
for (size_t j = 0; j < n; j++) {
BN_init(&buf[i][j]);
}
}

for (size_t i = 0; i < n; i++) {
current_pos = 1 - current_pos;
current = buf[current_pos];
previous = buf[1 - current_pos];

printf("|");
for (size_t j = 0; j < n; j++) {
if (i == 0 || j == 0) {
BN_one(&current[j]);
} else {
BN_add(&current[j], &previous[j], &current[j - 1]);
}
char* to_str = BN_bn2dec(&current[j]);
printf("%s ", to_str);
free(to_str);
}
printf("|\n");
}

for (size_t i = 0; i < 2; i++) {
for (size_t j = 0; j < n; j++) {
BN_clear(&buf[i][j]);
}
}

return 0;
}

もし、gccを使っているならどちらも-std=c99で、C99標準のコードであることを明示しないとコンパイルできません。

回答No.2

hanabutako

#include <err.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t get_value(uint64_t x, uint64_t y) {
if (x == 0 || y == 0) {
return 1;
}
return get_value(x - 1, y) + get_value(x, y - 1);
}

int
main(int argc, char *argv[])
{
if (argc != 2) {
errx(-1, "%s <n>", argv[0]);
}
int n = atoi(argv[1]);
for (int i = 0; i < n; i++) {
printf("|");
for (int j = 0; j < n; j++) {
printf("%lu ", get_value(i, j));
}
printf("|\n");
}

return 0;
}

n = 5くらいだったら、これで十分でしょう。

回答No.1

Tacosan

int a[5][5] = {
{ 1, 1, 1, 1, 1 },
{ 1, 2, 3, 4, 5 },
/* 以下省略 */
};