1

I'm currently doing the this problem for own practice. I manage to pass all the testcases, so I can't figure out whats wrong. My code is:

#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;
}

for exampel when I input 1000 I get 178 and 10000 I get 1762.

Input Sample

0
1
5
10
100

Output Samle

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

For each case, display the case number followed by the number of decimal digits required to represent the integer portion of the circumference for the given number of iterations. Follow the format of the sample output.

BrainStone
  • 3,028
  • 6
  • 32
  • 59
user3664730
  • 45
  • 1
  • 8

2 Answers2

5

The reason you get the wrong result is, as described earlier: you get overflow by using pow, but also because you - as you seem to have realized - used 3 as your start side length.

Here is an alternative, and correct, solution that is a bit shorter (without overflow):

The circumference (or perimeter) P(n) of a Sierpinski triangle of order n >= 0 can be shown to be:

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

I don't provide a proof since it's not necessary to solve the problem. However, it's rather easy to understand that this must be the case. One way is by calculating the perimeter of the first few orders of the Sierpinski triangle: 3, 9/2, 27/4, 81/8, ..., another is to think about how the circumference changes when you (1) "shrink" the shape by a factor of ½ and (2) "extend" the triangle by a factor of 3.

The number of digits D(x) in any natural number (of base 10) x is:

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

So to calculate the number of decimal digits in the Sierpinski perimeter of order n we calculate the number of digits in the integer part of P(n) = 3^(n + 1) / 2^n, i.e. D(floor(P(n))), which is also the solution to the problem:

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++ implementation that solves the problem: 

/** 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++;
    }
}
Prantare
  • 51
  • 1
  • 3
  • Even though this question is just over half a year old the answer is execellent. Especially considering you simplyfied the problem mathematically first. Finally I have a little recommendation: Use static constants for the log10 values. Then you can simplyfy the expression even further: ``n * (log10_3 - log10_2) + log10_3``. Saving ``log10_3 - log10_2`` to yet another constant and getting rid of ``log10_2`` would improve it even further! – BrainStone Mar 19 '16 at 15:56
  • Thank you! That's definitely a correct and alternative way to approach that expression. :-) – Prantare Mar 21 '16 at 20:32
2

You are overflowing the value of triangels. When you have

long double triangels = pow(3,shrinks);

Where shrinks = 10000 gives: 1.6313501853426258743032567291812e+4771.

The range of a long double where sizeof(long double) == 8 is 1.7E +/- 308.

More than likely you will need to use modular exponentiation to solve this problem.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • Do you have guide on how to use it ? – user3664730 Jul 13 '15 at 15:38
  • I don't personally have one but a quick google search give this SO question which looks good: http://stackoverflow.com/questions/2207006/modular-exponentiation-for-high-numbers-in-c – NathanOliver Jul 13 '15 at 15:40
  • And i dont understand why output sample is 1 when input sample is 1. Because at stage 1 its 9 + (1,5 *3) which is 13.5 so the integer part is 2. – user3664730 Jul 14 '15 at 06:48
  • @user3664730 At iteration 0 we have a circumference of 3 as we have 3 1 unit sides. At iteration 1 we remove the center triangle which gives us 3 triangles with sides of .5 so we have `3*3*.5` or 4.5 which can be represented by 1 integer place. – NathanOliver Jul 14 '15 at 12:00
  • That solved the problem! I read the text as if each side was 3 instead of 1. Thanks for the help! – user3664730 Jul 14 '15 at 18:58