谢尔宾斯基三角形的周长

Question

我目前正在做 this problem 练习。我设法通过了所有测试用例，所以我不知道出了什么问题。我的代码是：

#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
int main(){
   int num = 1;

   while(true){
    string line,stringRes;
    getline(cin,line);
    if(cin.eof()){break;}
    long double shrinks = atof(line.c_str());

    long double triangels = pow(3,shrinks);
    long double length = 3/pow(2,shrinks);
    long double res = floor(triangels* length * 3);
    int i = 0;
    while(res >= 10){
        i++;
        res =  res/10;
    };
    if(shrinks == 1){
        printf("Case %d: %d\n",num ,1);
    }else{
        printf("Case %d: %d\n",num ,i+1);
    }
    num++;
}
return 0;
}

例如，当我输入 1000 时得到 178，输入 10000 时得到 1762。

输入样本

输出样本

Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 3
Case 5: 19

对于每个案例，显示案例编号，后跟表示给定迭代次数的圆周整数部分所需的小数位数。遵循示例输出的格式。

Answer 1

您正在溢出 triangels 的值。当你有

long double triangels = pow(3,shrinks);

其中 shrinks = 10000 给出：1.6313501853426258743032567291812e+4771.

long double 的范围 sizeof(long double) == 8 是 1.7E +/- 308。

您很有可能需要使用 modular exponentiation 来解决这个问题。

Answer 2

如前所述，您得到错误结果的原因是：使用 pow 会溢出，而且还因为您 - 正如您似乎已经意识到的那样 - 使用 3 作为起始边长。

这是一个替代的、正确的解决方案，它更短一些（没有溢出）：

n >= 0 阶谢尔宾斯基三角形的周长（或周长）P(n) 可以表示为：

P(n) = 3^(n + 1) / 2^n

我不提供证据，因为它不是解决问题的必要条件。但是，很容易理解必须是这种情况。一种方法是通过计算谢尔宾斯基三角形前几阶的周长：3、9/2、27/4、81/8、...，另一种是想当您 (1) "shrink" 形状的 ½ 倍和 (2) "extend" 三角形的 3 倍时，周长如何变化。

任何自然数（以 10 为底）x 的位数 D(x) 是：

D(x) = 1 + floor(log10(x))

所以为了计算n阶谢尔宾斯基周长的小数位数，我们计算P(n) = 3^(n + 1) / 2^n的整数部分的位数，即D(floor(P(n)))，即还有问题的解决方法：

D(floor(P(n))) = 1 + floor(log10(3^(n + 1) / 2^n)) = /log(a/b) = log(a) - log(b)/ =
= 1 + floor(log10(3^(n + 1)) - log10(2^n)) = /log10(a^b) = b * log10(a)/ =
= 1 + floor((n + 1) * log10(3) - n * log10(2))

解决问题的C++实现：

/** Calculates the number of digits in the integer part of the perimeter of the Sierpinski triangle of order n */
/** Author: Fredrik Präntare, Date: 19/3/2016 */
#include <iostream>
#include <algorithm> // log10, floor
using namespace std;

int main(){
    int c = 1, n;
    while(scanf("%d", &n) != EOF){
        int D_p = 1 + floor((n + 1) * log10(3) - n * log10(2));
        printf("Case %d: %d\n", c, D_p);
        c++;
    }
}

谢尔宾斯基三角形的周长

Circumference of Sierpinski triangle

c++

math

c++11

c++14