C05

Exercise 00 : ft_iterative_factorial
• Create an iterated function that returns a number. This number is the result of a factorial operation based on the number given as a parameter.

int	ft_iterative_factorial(int nb)
{
	int					i;
	unsigned long long	result;

	i = 2;
	result = 1;
	if (nb < 0)
		return (0);
	else if (nb < 2)
		return (1);
	while (i <= nb)
		result *= (unsigned long long) i++;
	return (result);
}

반복문을 이용한 팩토리얼 반환
팩토리얼이 커질 수 있기 때문에 최대한 크게 unsigned long long
0! = 1 주의

Exercise 01 : ft_recursive_factorial
• Create a recursive function that returns the factorial of the number given as a parameter.

int	ft_recursive_factorial(int nb)
{
	if (nb < 0)
		return (0);
	else if (nb < 2)
		return (1);
	else
		return (nb * ft_recursive_factorial(nb - 1));
}

재귀를 이용한 팩토리얼 반환

Exercise 02 : ft_iterative_power
• Create an iterated function that returns the value of a power applied to a number.

int	ft_iterative_power(int nb, int power)
{
	int	result;
	int	i;

	result = nb;
	i = 1;
	if (power < 0)
		return (0);
	if (power == 0)
		return (1);
	if (nb == 0)
		return (0);
	while (i < power)
	{
		result *= nb;
		i++;
	}
	return (result);
}

반복문을 이용한 거듭제곱 수 반환
0의 0제곱이 1인 경우만 조심해서 조건 작성하면 된다.

Exercise 03 : ft_recursive_power
• Create a recursive function that returns the value of a power applied to a number.

int	ft_recursive_power(int nb, int power)
{
	if (power < 0)
		return (0);
	if (power == 0)
		return (1);
	if (nb == 0)
		return (0);
	return (nb * ft_recursive_power(nb, power - 1));
}

재귀를 이용한 거듭제곱 반환

Exercise 04 : ft_fibonacci
• Create a function ft_fibonacci that returns the n-th element of the Fibonacci sequence, the first element being at the 0 index. We’ll consider that the Fibonacci sequence starts like this: 0, 1, 1, 2.

int	ft_fibonacci(int index)
{
	if (index < 0)
		return (-1);
	if (index == 0)
		return (0);
	if (index == 1)
		return (1);
	return (ft_fibonacci(index - 1) + ft_fibonacci(index - 2));
}

인덱스에 따른 피보나치 수 반환
초기값을 두개 리턴해줘야한다.

Exercise 05 : ft_sqrt
• Create a function that returns the square root of a number (if it exists), or 0 if the square root is an irrational number.

int	ft_sqrt(int nb)
{
	long	i;
	long	temp;

	i = 0;
	temp = 0;
	if (nb < 1)
		return (0);
	while (1)
	{
		temp = i * i;
		if (temp == nb)
			return (i);
		else if (temp > nb)
			return (0);
		i++;
	}
}

특정 숫자의 제곱근이 있다면 반환, 없으면 0 반환
i제곱이 nb 초과하면 0리턴, 같다면 i리턴

Exercise 06 : ft_is_prime
• Create a function that returns 1 if the number given as a parameter is a prime number, and 0 if it isn’t.

int	is_prime(int num)
{
	long	i;
	long	temp;

	i = 2;
	if (num <= 1)
		return (0);
	if (num == 2)
		return (1);
	while (1)
	{
		if (num % i == 0)
			return (0);
		temp = i * i;
		if (temp > num)
			break ;
		i++;
	}
	return (1);
}

소수 판별
소수의 정의는 원래 1과 자기 자신을 제외하고 어떤 수로도 나누어 떨어지지 않아야 한다 인데...
그렇다고 2 ~ nb-1을 모두 나누어 보면 너무 시간낭비
모든 약수가 짝을 지어있다는 걸 이용해보면
sqrt(nb) 이전까지 나누어보면 그 이상을 의미가 없다.
즉 sqrt(nb) 보다 큰 수로 나누어 떨어진다고 하더라도 그 수는 어짜피 sqrt(nb)보다 작은 어떤 수로 나누었을때의 몫일테니까...
그래서 sqrt때와 마찬가지로 i를 증가시키면서 nb가 i로 나누어떨어지면 0반환(소수가 아님) 그리고 i의 제곱이 nb를 초과하면 반복문에서 나와서 1반환
-> 반복문에서 나오지 않고 바로 1을 리턴했으면 1줄 줄였겠다.

Exercise 07 : ft_find_next_prime
• Create a function that returns the next prime number greater or equal to the number given as argument.

int	is_prime(int num)
{
	long	i;
	long	temp;

	i = 2;
	if (num <= 1)
		return (0);
	if (num == 2)
		return (1);
	while (1)
	{
		if (num % i == 0)
			return (0);
		temp = i * i;
		if (temp > num)
			break ;
		i++;
	}
	return (1);
}

int	ft_find_next_prime(int nb)
{
	int	result;

	result = nb;
	while (1)
	{
		if (is_prime(result))
			return (result);
		result++;
	}
}

주어진 숫자보다 같거나 큰 소수 중 가장 작은 값
즉 바로 다음 소수를 찾는 문제이다
효율적인 어떤 방법이 있을까 계속 고민했지만 못찾고 그냥 무식하게 1씩 증가시키면서 소수판별...

Exercise 08 : ft_ten_queens_puzzle
• Create a function that displays all possible placements of the ten queens on a chessboard which would contain ten columns and ten lines, without them being able to reach each other in a single move, and returns the number of possibilities.

#include <unistd.h>

void	print_array(int *arr)
{
	int		i;
	char	c;

	i = 0;
	while (i < 10)
	{
		c = arr[i] + '0';
		write(1, &c, 1);
		i++;
	}
	write(1, "\n", 1);
}

int	check(int col, int *arr)
{
	int	i;

	i = 0;
	while (i < col)
	{
		if (arr[i] == arr[col])
			return (0);
		if (arr[i] - arr[col] == i - col)
			return (0);
		if (arr[i] - arr[col] == col - i)
			return (0);
		i++;
	}
	return (1);
}

int	recursive_func(int depth, int *arr)
{
	int	i;
	int	count;

	i = 0;
	count = 0;
	if (depth == 10)
	{
		print_array(arr);
		return (1);
	}
	while (i < 10)
	{
		arr[depth] = i;
		if (check(depth, arr))
			count += recursive_func(depth + 1, arr);
		i++;
	}
	return (count);
}

int	ft_ten_queens_puzzle(void)
{
	int	arr[10];
	int	i;
	int	result;

	i = 0;
	result = 0;
	while (i < 10)
		arr[i++] = 0;
	i = 0;
	while (i < 10)
	{
		result += recursive_func(1, arr);
		arr[0]++;
		i++;
	}
	return (result);
}

유명한 n-queen 문제에서 n을 10으로 고정한 문제다. 퀸의 위치가 저장된 배열을 모두 반환하고 총 경우의수를 반환하는 함수를 작성
재귀를 통해서 작성하는 간단한 문제였는데 메인 함수에서 초기값을 넣는 과정에서 while을 썼는데 굳이 그렇게 하지 않고 depth를 0부터 시작해서 재귀를 돌았어도 됐다. 그러면 코드 몇줄은 아꼈겠다...