n桁以下の最大の3のべき乗

Question

正整数 n ( 0 < n < 80 ) に対して, n桁以内の最大の３のベキ乗数を左詰めで書き出すプログラムを作れ。

【入力】
正整数 n ( 0 < n < 80 ) １つ。

【出力】
１行として書き出す（末尾に改行を書き出すこと）。

【例】
入力１
1
出力１
9

が問題と出力結果です。自分のコードで納得いっているのですが出力が上手くいきません。どこが間違っているのか指摘していただきたいです。

#include <stdio.h>

int main(void){
    int n;
    scanf("%d", &n);
    int x=1;
    int i;
    int digit=0;
    for(i=0;i<1000;i++){
        x=x*3;
        while(x!=0){  //xの桁数を計算
            x=x/10;
            ++digit;
        }
        if(digit>n+1){
            break;
        }
    }
    printf("%d\n", x/3);  //最後nよりも1桁多い最小のxだから割る3
    return 0;
}

Answer 1

あちこちおかしいです。変数の役割を自分で把握仕切れていないのが原因。

・xはどんどん3を掛けていく変数のつもりだったはずなのに、0になるまで10で割っている
・桁数を数えるはずのdigitが、数える毎じゃなくてプログラムの最初に一度だけしか初期化されていない
・n桁を越えたら止めるはずが、n+1を越えたら止めることになっている

を直せば、int型の扱える数値の範囲内では上手く行きます。普通は10桁くらいです。long long intであっても19桁くらいが限界。

Comments

[otn]

何乗するかは、(int)(n * log(10)/log(3)) で求まるので、あとは3のこれ乗をどうやって計算するか。
long doubleとかを使っても80桁は無理なので、工夫が要りますね。

[nagano-yuhi]

ありがとうございます。もう一度考えてみます。

[otn]

実用的には、多倍長計算のgmpライブラリを使うのでしょうが、今回はなんらかの課題の問題なわけで、何の課題かによって、gmpを使うのが適当なのか、課題にに沿った別のやり方をすべきなのかがわかりません。

Answer 2

x = x * 3;
while (x != 0) {  //xの桁数を計算
    x = x / 10;
    ++digit;
}

一周目でxを0にしているので、0のまま1000回ループしています。
桁数をカウントし直す際にdigitをリセットしていません。

if(digit>n+1)

入力値+1桁で判定しています。

Comments

[nagano-yuhi]

ありがとうございます。もう一度考えてみます。

Answer 3

桁数判定はxとは別の変数xtempに移してやったほうがいいと思います。
xを書き換えられると不都合なためです。
また, digitは桁数計算の前に初期化する必要があります。

intだと桁数が余裕で足りないので、long longにしました。
ですが、それでもn>18の場合にはオーバーフローして正しい答えが出ませんので、n>18の答えも正しく出したい時には多倍長整数の計算が必要になります。

#include <stdio.h>

int main(void) {
  long long n;
  scanf("%lld", &n);
  long long x = 1LL;

  for (long long i = 0; i < 1000; i++) {
    x = x * 3LL;

    long long xtemp = x;
    long long digit = 0;

    while (xtemp != 0) {  // xの桁数を計算
      xtemp /= 10LL;
      ++digit;
    }

    if (digit > n) {
      break;
    }
  }
  printf("%lld\n", x/3LL);  //最後nよりも1桁多い最小のxだから割る3
  return 0;
}

私の実装例

#include <assert.h>
#include <stdio.h>

int main(void)
{
  long long n;
  scanf("%lld", &n);

  if (n <= 0 || n >= 18) {
    printf("範囲外です");
    return 0;
  }

  long long end_ndigit = 1;

  for (long long i = 0; i < n; i++) {
    end_ndigit *= 10LL;
  }

  long long x = 1LL;
  while (x < end_ndigit) {
    x *= 3LL;
  }

  printf("%lld\n", x / 3LL); //最後nよりも1桁多い最小のxだから割る3
  return 0;
}

GNU MPで組んでみました

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

int main(void)
{
  long long n;
  scanf("%lld", &n);
  if(n<=0){
    printf("n must be positive.\n");
    return 0;
  }
  // 10**nを計算しておく
  mpz_t end_ndigit;
  mpz_init(end_ndigit);
  mpz_set_ui(end_ndigit, 1);
  for (long long i = 0; i < n; i++) {
    mpz_mul_ui(end_ndigit, end_ndigit, 10);
  }

  // 3をかけ続け, 桁数がnを超えたら抜ける
  mpz_t x;
  mpz_init(x);
  mpz_set_ui(x, 1);
  while (mpz_cmp(x, end_ndigit) < 0) {
    mpz_mul_ui(x, x, 3);
  }

  // 答え
  mpz_cdiv_q_ui(x, x, 3);
  gmp_printf("%Zd\n", x);

  // 解放 
  mpz_clear(x);
  mpz_clear(end_ndigit);
  return 0;
}

80
47780373265559358009192445772039644256794138579444188363337645975725833060824587

Comments

[nagano-yuhi]

丁寧な回答ありがとうございます！！！