How do I solve this C language question?

Question

2.33/5 (3 votes)

See more:

fun(1)=100,fun(2)=101;
fun(3)=fun(2)+fun(1);
fun(4)=fun(3)+fun(2);
fun(n)=fun(n-1)+fun(n-2);
Write a program to calculate fun(100)

What I have tried:

C++

#include<stdio.h>

int fun(int n)
{
if (n > 109)
	return n - 10;
return fun(fun(n+11));
}

int main()
{
printf(" %d ", fun(100));
getchar();
return 0;
}

Posted 2-Jan-23 18:26pm

D Square 2023

Updated 5-Jan-23 9:32am

Michael Haephrati

v3

Add a Solution

Comments

Graeme_Grant 3-Jan-23 1:24am

I see a for(...) loop.

CPallini 3-Jan-23 2:27am

Why did you try that?
I mean, the code you posted looks completely unrelated with the question.

4 solutions

Solution 1

Read the question again, and pay attention to the definition of fun(n)

Your code doesn't do that. or even close to that.
You might also want to look at the "termination rules" as set in the question if you want to avoid an theoretically infinite loop (that'll actually end pretty soon when your app crashes with a "out of stack space" error).

[edit]
By the way: you might want to think carefully here: a standard 32 bit integer will overflow at fun(37) ...
[/edit]

Posted 2-Jan-23 18:57pm

OriginalGriff

Updated 2-Jan-23 19:05pm

v2

Comments

CPallini 3-Jan-23 2:25am

5.

Solution 3

You should use 128 bit variables (or a big integer library) to compute the result, since, as pointed out by Griff, 32 bit integers overflows at input = 37 (and 64 bit ones overflow as well, at input = 83).
Then you should avoid (at least a naive) recursive approach, using instead an iterative one.
You may search for 'iterative approach to Fibonacci numbers' in order to see working code examples for such (very similar) problem.

Posted 5-Jan-23 6:29am

CPallini

Solution 4

Quote:
How do I solve this C language question?

Advice: First of all, make sure that you understand the requirement.
Then calculate by hand the few first answers of the requirement, say from fun(-1) to fun(10).
Then as you have written the code, check the answers with your hand calculation.

To help you to understand what your code is really doing, there is a tool, its name is Debugger.

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.

Posted 5-Jan-23 9:32am

Patrice T

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Michael Haephrati · Accepted Answer · 2023-01-05T00:45:00

Solution 2

The question wasn't clear and I edited it. There were typos.

I suggest the following:

#include <iostream>

int fun(int n) 
{
   if (n <= 0) 
   {
      return -1; // handle negative input
   } 
   else if (n == 1) 
   {
      return 100;
   } 
   else if (n == 2) 
   {
      return 101;
   } 
   else 
   {
      return fun(n-1) + fun(n-2);
   }
}

int main() 
{
   std::cout << fun(100) << std::endl;
   return 0;
}

Posted 5-Jan-23 0:45am

Michael Haephrati

Updated 5-Jan-23 1:58am

v2

Comments

CPallini 5-Jan-23 7:08am

What about fun(-42) ?

Michael Haephrati 5-Jan-23 7:59am

The OP specifically asked: "Write a program to calculate fun(100)", however I updated my solution. Thanks

CPallini 5-Jan-23 11:05am

5.However, now your code suffers of the problem pointed out by Griff: even on a 64 bit machine, int is 32-bit wide. The code stops working properly when input is 37.
Moreover, a simple recursive approach, for fun(100) is computationally prohibitive.

How do I solve this C language question?

4 solutions

Solution 1

Solution 3

Solution 2

Solution 4

Add your solution here

Preview 0

How do I solve this C language question?

4 solutions

Solution 1

Solution 3

Solution 2

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us