Sierpinski三角形的周长

Question

我正在为自己的实践做这个问题.我设法通过所有的测试用例,所以我无法弄清楚什么是错的.我的代码是:

#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.

输入样本

0
1
5
10
100

输出Samle

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

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

Answer 1

你得到错误结果的原因是,如前所述:你通过使用pow得到溢出,但也因为你 - 你似乎已经意识到 - 使用3作为你的起始边长度.

这是一个替代的,正确的解决方案,它有点短(没有溢出):

P(n)Sierpinski三角形的圆周(或周长)n >= 0可以显示为:

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

我没有提供证据,因为没有必要解决问题.但是,很容易理解必须如此.一种方法是通过计算谢尔宾斯基三角形的前几个订单的周长:3,9/2,27/4,81/8,...,另一个是思考的圆周,当你(1)的一个因素"缩水"的形状如何变化和半(2)将三角形"延伸"3倍.

D(x)任何自然数(基数为10)的位数x为:

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

因此,为了计算Sierpinski周长的小数位数,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++;
    }
}