C言語 10進で出力

Question

###質問したい事

整数n(1を超え10000未満)を入力した時、その整数桁未満の3のべき乗でもっとも大きいものを出力するようにするにはどう書けば良いか教えてください。

例
入力　15
出力　68630377364883

入力　26
出力　6461081889226673298932241

#include <stdio.h>

#define N 10000

．．．

int main(void)
{
   

Comments

[退会済みユーザー]

https://teratail.com/help/avoid-asking

> コードをください・デバッグしてください等の丸投げの質問
>
> 何かを作りたいのでコードを書いてほしい、学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。
> 問題や質問は実際に調査や作業に取り組み、具体的なところで生まれると考えるためです。
> まずは実際に作業に取り組み、つまづいたところで投稿をしてみてください。

[raccy]

https://teratail.com/questions/256617
上の3の冪乗版ということですか？

[ta-9]

raccyさんご質問ありがとうございます。
その質問はｎ以下のようですが今回のはｎの桁数未満です。

[raccy]

例では15桁未満では9となっていますが、15桁未満でもっとも大きい3の冪乗は3の29乗の68630377364883になると思うのですが、問題文または例のどちらかが間違ってませんか？

[ta-9]

15は2桁なので2桁未満(=1桁)で最大の3のべき乗は9です。

[raccy]

つまりは、15は「9以下」、126は「99以下」の最大の3のべき乗を計算して出力する、ということであってますか？それなら、入力されたnに対して、nより1桁すくない「9...9以下」がわかれば、2のべき乗と同じ方法で解けませんか？

[raccy]

あと、1～9の場合は、1桁未満、つまり0桁ですが、3の0乗でも1なので、解なしになると思われるのですが、その場合は、どのような出力になるのですか？

[ta-9]

勘違いしていました。申し訳ございません。
正しくは　15は15桁という意味でそれの桁未満(＝14桁)の最大なので出力は「68630377364883」です。
もう一つの例も同様の意味です。

質問の例の値を修正させて頂きました。

[raccy]

26のときは6461081889226673298932241ではないのですか？引用元も何も書いていないので、この問題文はあなたが考えたのですよね？質問や例が正確ではないと、何が正解なのかを判断できません。最大で9999桁の数字を出力する問題と言うことであってますか？

[ta-9]

失礼しました。26の時の最大は6461081889226673298932241でした。
nの範囲は1<ｎ<10000で間違いありません。ただ9999桁の出力では無くｎ未満の為出力最大桁数は9998桁になります。

Answer 1

3倍を繰り返すだけの多倍長計算は簡単です。遅いけど。

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

int main(void)
{
	int a[10000];
	int n;
	if (scanf("%d", &n) != 1 || n <= 1 || n >= 10000) return 1;
	int k = --n / log10(3);
	a[0] = 1;
	for (int i = 1; i < n; i++) a[i] = 0;
	for (int i = 0; i < k; i++)
		for (int c = 0, j = 0; j < n; j++)
			a[j] = a[j] * 3 + c, c = a[j] / 10, a[j] %= 10;
	while (--n >= 0) printf("%d", a[n]);
	putchar('\n');
}

理解できない場合は、どこが分からないのかを必ず質問してください。

Answer 2

出力される数値はunsigned long longを遥かに超えます。これを実現するには、多倍長整数を実装するか、一桁づつ計算することになります。一桁ずつ計算は無駄も多く、多倍長整数を自分で実装するのは大変なので、適当な多倍長整数ライブラリを使った方が早いです。下記はGMPを使った場合です。

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

int main(void)
{
	int n;
	if (scanf("%d", &n) != 1 || n <= 1 || n >= 10000) return 1;
	int e = (n - 1) / log10(3);
	mpz_t x;
	mpz_init(x);
	mpz_ui_pow_ui(x, 3, e);
	mpz_out_str(stdout, 10, x);
	mpz_clear(x);
	printf("\n");
	return 0;
}

Comments

[ta-9]

ご回答ありがとうございます。助かります。
ただコンパイルエラーとなる為、もう少し考えてみます。
(GMPファイルを上手くインストール出来ないのが原因かも)