2
\$\begingroup\$

Siruri2 | www.pbinfo.ro

Fibonacci, a famous Italian mathematician in the Mediaeval Era, had discovered a series of natural numbers with multiple applications, a string that bears his name:

Fibonacci (n) = 1, if n = 1 or n = 2 Fibonacci (n) = Fibonacci (n−1) + Fibonacci (n−2), if n>2

Fascinated by Fibonacci's line, and especially the applications of this string in nature, Iccanobif, a mathematician in the making, created a string and he named him:

Iccanobif (n) = 1, if n = 1 or n = 2 Iccanobif (n) = reversed (Iccanobif (n-1)) + reversed (Iccanobif (n-2)), if n > 2

Obtaining the following rows:

Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Iccanobif: 1, 1, 2, 3, 5, 8, 13, 39, 124, 514, 836, ...

Iccanobif now wonders which number has more natural divisors: the n-th term in the Fibonacci row or the n-th term in the Iccanobif row. Requirements:

Write a program that reads n natural number and displays:

a) the n-th term in Fibonacci's row and its number of divisors

b) the n-th term of the Iccanobif string and its number of divisors

Input data

The input file siruri2.in contains on the first line a natural number p. For all input tests, the p number can only have a value of 1 or value 2. A natural number n is found on the second line of the file.

Output data

If the value of p is 1, only a) of the requirements will be solved. In this case, in the output file siruri2.out, the n-th term in Fibonacci string and its number of divisors will be written.

If the value of p is 2, only the point b) of the requirements will be solved. In this case, in the output file siruri2.out the n-th term in Iccanobif string and its number of divisors will be written Restrictions and clarifications

1 ≤ n ≤ 50 For the correct resolution of the first requirement, 50% of the score is awarded, and 50% of the score is awarded for the second requirement.

Limits: - time: 1 second; - memory: 2 MB/ 2 MB.

Example 1

siruri2.in

1 8

siruri2.out

21 4

Example 2

siruri2.in

2 9

siruri2.out

124 6

Explanations

For the first example: The eighth term in Fibonacci's string is 21 and 21 has 4 divisors. (p being 1 solves only requirement a)

For the second example: The ninth term in Iccanobif's string is 124, and 124 has six divisors. (p being 2 solves only requirement b)

Here is my code, which doesn't execute all given tests in time (exceeds time limit for 3 tests):

#include <iostream> #include <fstream> using namespace std; ifstream in("siruri2.in"); ofstream out("siruri2.out"); void numOfDivisors (long long n) { long numOfDivisors = 1, factor = 2; while (factor * factor <= n) { if (!(n % factor)) { long exponent = 0; while (!(n % factor)) { n /= factor; exponent ++; } numOfDivisors *= exponent + 1; } if (factor == 2) factor = 3; else factor += 2; } if (n > 1) { numOfDivisors *= 2; } out << numOfDivisors; } long long inverted (long long a) { long long b=0; while (a) { b = b * 10 + a % 10; a /= 10; } return b; } void fibonacci (short ord) { long long a = 1, b = 1; if (ord < 3) {out << "1 1";} else { ord -= 2; while (ord) { a+=b; ord--; if (!ord) { out << a << " "; numOfDivisors(a); break; } else { b+=a; ord--; if (!ord) { out << b << " "; numOfDivisors(b); } } } } } void iccanobif (short ord) { long long a = 1, b = 1; if (ord < 3) out << "1 1"; else { ord -= 2; while (ord) { a = inverted(a) + inverted(b); ord--; if (!ord) { out << a << " "; numOfDivisors(a); break; } else { b = inverted(a) + inverted(b); ord--; if (!ord) { out << b << " "; numOfDivisors(b); } } } } } int main() { short requirement, ord; in >> requirement >> ord; if (requirement == 1) fibonacci(ord); else iccanobif(ord); }
\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

Efficiency

numOfDivisors()

  • numOfDivisors and exponent do not need to be long. Using int is sufficient, and should be slightly faster.

  • n is a long long, where as factor is only a long. So factor will be repeated promoted to a long long for the operations n % factor and n /= factor. You might find a speed improvement by actually declaring factor as a long long to avoid the repeated type promotion.

  • factor is only a long, so factor * factor is also only a long, and may overflow when looping while (factor * factor <= n). Using a long long will avoid this, which may prevent the loop from running for a long time if n is prime and larger than a long.

  • If n % factor == 0, then the exponent counting inner loop is entered, and the first thing that is done is n % factor, which is already known to be zero. Using a do { ... } while (!(n % factor)); loop will prevent the redundant calculation.

  • The outer loop starts at n=2, and has an if statement to choose between incrementing n by 2, or setting it to 3. If 2 was handled as a special case, then the loop could unconditionally increment by 2, eliminating the if statement for another speed gain. To handle the 2^exponent case, simply count the number of trailing zeros in the binary representation of n.

  • Your factor finder is testing all odd numbers whose square is less than n. You only need to test factor numbers which are prime. Other than 2 & 3, all prime numbers can be generated from 6k-1 and 6k+1. Or maybe use a prime sieve ... you are allowed 2MB of memory ...

iccanobif()

You are computing...

while (...) { a = inverted(a) + inverted(b); // #1 ... b = inverted(a) + inverted(b); // #2 }

When you are executing statement #2, you've already computed inverted(b) during statement #1, above. If you cached that value, you wouldn't need to invert it a second time.

Similarly, when computing statement #1 in subsequent loops, you've already computed inverted(a) during statement #2, below, on the previous iteration. If you cached that value, you wouldn't need to invert it a second time.

General

Add vertical white space after #includes, after global variables, and between functions.

Add whitespace around operators. Ie, a += b; instead of a+=b;.

Don't use using namespace std;. Simply use:

std::ifstream in("..."); std::ofstream out("...");

numOfDivisors() should return the answer, not print the answer.

fibonacci() should return the Fibonacci value, not print the value and call another function which also has the side-effect of additional printing. Ditto for iccanobif().

main() is declare to return an int, but doesn't return anything.

If the above changes were made, then in and out don't need to be global variables; they could be made local to the main function:

void main() { std::ifstream("siruri2.in"); std::ofstream("siruri2.out"); short requirement, ord; in >> requirement >> ord; long long n = requirement == 1 ? fibonacci(ord) : iccanobif(ord); int num_divisors = numOfDivisors(n); out << n << ' ' << num_divisors; }
\$\endgroup\$
5
  • \$\begingroup\$ You only need to test factor numbers which are prime. Are you sure? I don't see six prime divisors in 124 \$\endgroup\$ Commented Dec 28, 2018 at 9:59
  • \$\begingroup\$ int is NOT necessarily faster than long. On all the major compilers for x86, which we're going to assume is used as nothing else was stated, sizeof(int)==sizeof(long). int is guaranteed to be at least 16 bits but in practice is almost always 32 bits on machines with a 32 bit native word size while long is guaranteed to be at least 32 bits and most often is, even on 64 bit machines. \$\endgroup\$ Commented Dec 28, 2018 at 10:49
  • \$\begingroup\$ @papagaga You are correct, 124 doesn’t have 6 prime divisors; it has two: 2 & 31. And if you look at numOfDivisors(), you’d see it determines 124 = 2^2 * 31^1, takes the exponents 2 & 1, adds one to each, and multiplies them all together: (2+1)*(1+1) = 6. So yes, I’m sure you only need to test factor numbers which are prime. \$\endgroup\$ Commented Dec 28, 2018 at 16:52
  • \$\begingroup\$ It's not prime divisors that I care about, it's all of the divisors. AJNeufield is right, but this is much easier to implement that what he suggested. Also, the program will find all my divisors just fine: 4 won't go through, because my number was already divided by 2 until it couldn't be divided anymore. This part of my code isn't the problematic one, but I will try all of your suggestions, as I'm still a learner. \$\endgroup\$ Commented Dec 29, 2018 at 8:57
  • 1
    \$\begingroup\$ Your problematic code is an infinite loop. But since this is the Code Review site, where working code gets reviewed, I gave you a review of all of the code. With only 50 numbers to test, and under one second per number, you could write a loop to test each number (instead of reading from a file), and identify which input is the problematic number is under 1 minute. Then, examine what happens with the problematic number. Then, re-read my review, taking extra care when I talk about that area of the code. I mention both the problem and solution. Or ask a debug help question on StackOverflow. \$\endgroup\$ Commented Dec 29, 2018 at 16:06
1
\$\begingroup\$

constexpr is your friend

You may feel like it's cheating, but C++ allows you to pre-compute the answers really easily with the constexpr keyword. A constexpr value must be known at compile-time, and a constexpr function, given a constexpr argument, will be executed at compile-time. It means that you can easily compute and store the 50 first terms of the fibonacci progression -and of the iccanobif progression for that matter- at compile-time. And you can of course calculate how many divisors they have. The beauty of it is that you don't need the most efficient algorithms: since all the work is done once and for all during compilation, being more readable and maintainable could very well be the right choice.

Here's a quickly-written constexpr answer to your problem: https://wandbox.org/permlink/qAtXS15Ir9c4vYgG

avoid duplicating code

Copy-and-paste is an anti-pattern because it is hard to maintain: if you find an improvement in your fibonacci function, you'll need to replicate it in the iccanobif function; at some point, you'll forget to copy, or to modify your copy. That's why you should try to factorize your code. In this case, both functions share most of their code; the only thing iccanobif does in addition is to reverse the previous terms. So you can rewrite both functions into one that decides whether to reverse the previous terms according to a function parameter.

\$\endgroup\$
4
  • \$\begingroup\$ Clever with the constexpr but they didn't give any limit on n so I find it hard to recommend it because of that. As choosing the right number to pre-compute is hard in this case. \$\endgroup\$ Commented Dec 28, 2018 at 10:57
  • \$\begingroup\$ @EmilyL. Restrictions and clarifications: 1 ≤ n ≤ 50... so please do recommend :-) \$\endgroup\$ Commented Dec 28, 2018 at 11:46
  • \$\begingroup\$ Oh I didn't see that due to the formatting, nvm then :) Still it's kinda cheating and defeating the purpose of the exercise ;p \$\endgroup\$ Commented Dec 28, 2018 at 11:52
  • \$\begingroup\$ It is also, however, quite wrong: 1836311903 + 2971215073 != 512559680 as just one example. \$\endgroup\$ Commented Dec 28, 2018 at 17:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.