Как составить программу для вычисления факториала - Исправление недочетов и поиск решений вместе с Examum.ru

n! Факториал

Написать программу на C++ для вычисления(нахождения или решения) факториала — это очень популярное задание в сборниках по обучению программированию. Решение этой задачи и многих других размещено в разделе с решениями задач по программированию на C++. В данной статье мы разберем как реализовать решение на языке программирования C++.

Для начала — что такое факториал?

Факториал — это произведение всех натуральных чисел от 1 до N включительно. То есть, если N = 5, то значение факториала

F = 1*2*3*4*5 = 120.

Решить данную задачу можно несколькими способами, мы рассмотрим рекурсивное вычисление факториала и циклическое.

До начала вычислений необходимо узнать N. N может быть больше или равно единице (N>=0). Поэтому для начала напишем каркас приложения, которое будет получать значение N и проверять его. Если N не соответствует, то программа выдаст ошибку «Error: N < 0.«. Листинг программы следующий:

#include <iostream>

using namespace std;

int main()
{
	int N; // Объявляем переменную N целочисленного типа
	cout << "N = ";
	cin >> N; // Присваиваем введенное значение в переменную
	
	if(N >= 0)
	{
		// Здесь будет код, вычислящий факториал
	}
	else
	{
		cout << "Error: N < 0."; // Выводим ошибку, т.к. N < 0
	}
	
	return 0;
}

Проверим ее.

Компилируем, запускаем и вводим любую N, которая меньше 0.

Значение N = -5

Получили ошибку, программа сообщила, что N < 0.

Запускаем и вводим любую N, которая больше или равно 0.

Значение N = 5

Программа ничего не вывела после, значит выполнился участок кода, где написано «Здесь будет код…«.

Теперь нам достаточно вставить в место, где написано «Здесь будет код…» нужную реализацию алгоритма по нахождению факториала.

Нахождение факториала с помощью цикла

Для нахождения факториала напишем свою функцию, которая будет принимать значение N и возвращать результат.

Реализовать алгоритм нахождения факториала очень просто:

int factorial(int N)
{
	int F = 1; 
	
	for(int i=1; i<=N; ++i)
	{
		F *= i; // Эквивалент F = F*i;
	}
	return F; // Возвращаем ответ
}

Что делает функция? Принимает значение N, после чего определяется переменная F, она будет хранить в себе ответ. Запускается цикл for от 1 до N, то есть переменная i будет иметь значения от 1 до N, эти значения мы используем для перемножения переменной F.

Для N=0 значение факториала равно 1. Цикл не будет вообще выполняться, т.к. i должна быть меньшей или равной N, в данном случае первое значение i=1, а N=0. Функция просто возвратит F, которая равно 1.

Для N=1 значение факториала равно 1. Цикл выполнится 1 раз, произойдет умножение F на i, а так как первое значение i = 1, то F так и останется равна 1.

Для остальных значений N цикл будет выполняться N раз, с каждой итерацией i будет увеличиваться на 1 и умножать на себя F.

(F = F*i).

Вставляем функцию в нашу программу:

#include <iostream>

using namespace std;

//Начало функции нахождения факториала
int factorial(int N)
{
	int F = 1;
	
	for(int i=1; i<=N; ++i)
	{
		F *= i;
	}
	return F;
}
//Конец функции нахождения факториала

int main()
{
	int N;
	cout << "N = ";
	cin >> N;
	
	if(N >= 0)
	{
		cout << factorial(N); // Тут мы передаем нашей функции N и выводим ответ
	}
	else
	{
		cout << "Error: N < 0.";
	}
	
	return 0;
}

Теперь проверим работу программы, для этого скомпилируем, запустим и попробуем ввести различные значения.

Пусть найдет факториал от 0

Факториал от 0

Получили значение 1. Мы знаем, что факториал от 0 равен единице, здесь программа работает верно.

Пусть найдет факториал от 1

Факториал от 1

Получили значение 1. Мы знаем, что факториал от 1 равен единице, здесь программа тоже работает верно.

Пусть найдет факториал от 5

Факториал от 5

Получили значение 120. Проверим: F = 1*2*3*4*5 = 120. Программа верно вычислила факториал.

Рекурсивное нахождение факториала

Для такого способа мы тоже напишем функцию, но она не будет содержать цикла. Рекурсивная функция — это функция, которая вызывает сама себя.

Наша функция factorial() будет принимать значение N и возвращать N*factorial(N-1). То есть будет возвращать значение N умноженное на саму себя, но только с N-1.

Код реализации рекурсивной функции нахождения факториала

int factorial(int N)
{
	if(N==0) return 1; // Если factorial(0), то возвращаем 1
	if(N==1) return 1; // Если factorial(1), то возвращаем 1
	return N*factorial(N-1); // А если нет, то возвращаем значение N*factorial(N-1)
}

Как это работает?

Допустим, N = 3. Мы передаем значение функции factorial(3), а она возвращает значение 3 * factorial(2), в свою очередь factorial(2) возвращает 2 * factorial(1), а factorial(1) возвращает 1. И теперь мы идем в обратном порядке:

factorial(1) = 1;

factorial(2) = 2 * factorial(1) = 2 * 1 = 2;

factorial(3) = 3 * factorial(2) = 3 * 2 = 6;

Вызванная функция factorial(3) возвратит нам 6.

А factorial(0) и factorial(1) сразу вернут 1.

Вставим рекурсивную функцию в программу для нахождения факториала:

#include <iostream>

using namespace std;

// Начало рекурсивной функции нахождения факториала
int factorial(int N)
{
	if(N==0) return 1;
	if(N==1) return 1;
	return N*factorial(N-1);
}
// Конец функции

int main()
{
	int N;
	cout << "N = ";
	cin >> N;
	
	if(N >= 0)
	{
		cout << factorial(N); // Передаем функции N и выводим результат
	}
	else
	{
		cout << "Error: N < 0.";
	}
	
	return 0;
}

Компилируем, запускаем и проверяем.

Значение факториала для 0

Факториал от 0

Вывела 1, а мы знаем, что факториал от 0 равен 1. Значит работает верно.

Значение факториала для 1

Факториал от 1

Вывела 1, а мы знаем, что факториал от 1 равен 1. Значит работает верно.

Значение факториала для 5

Факториал от 5

Получили значение 120. Проверим:

F = 1*2*3*4*5 = 120.

Программа верно вычислила факториал.

Послесловие

Итак, мы написали две функции разными способами, которые выполняют решают одну и ту же задачу — вычисление значения факториала. Эта задача входит в список с решениями задач по программированию, если вам нужно решить еще задачу — загляните туда, возможно вы найдете нужное решение. Если остались вопросы, то задавайте их в комментариях.

Источник

The factorial program in C of a non-negative integer is the multiplication of all integers smaller than or equal to n. In this article, we will learn how to find the factorial of a number using the C program.

Example:

Factorial of 6 is 6*5*4*3*2*1 which is 720.

Method to Find Factorial of a Number

There are multiple methods to find the factorial of a Number as mentioned below:

Iterative Solution
Recursive Method
Tgamma() Method
Using Pointers

1. Iterative Solution

Factorial can also be calculated iteratively as recursion can be costly for large numbers. Here we have shown the iterative approach using both for and while loops.

i). Factorial Program Using For Loop in C

C

#include <stdio.h>

unsigned int factorial(unsigned int n)

{

int res = 1, i;

for (i = 2; i <= n; i++)

res *= i;

return res;

}

int main()

{

int num = 5;

printf("Factorial of %d is %d",

num, factorial(num));

return 0;

}

Output

Factorial of 5 is 120

The Complexity of the Method

Time Complexity: O(n)

Auxiliary Space: O(1)

ii). Factorial Program Using While loop in C

C

#include <stdio.h>

unsigned int factorial(unsigned int n)

{

if (n == 0)

return 1;

int i = n, fact = 1;

while (n / i != n) {

fact = fact * i;

i--;

}

return fact;

}

int main()

{

int num = 5;

printf("Factorial of %d is %d",

num, factorial(num));

return 0;

}

Output

Factorial of 5 is 120

The Complexity of the Method

Time Complexity: O(n)

Auxiliary Space: O(1)

2. Using Recursive Solution

Factorial can be calculated using the following recursive formula.

  n! = n * (n-1)!
  n! = 1 if n = 0 or n = 1

i). Factorial Program Using Recursion in C

C

#include <stdio.h>

unsigned int factorial(unsigned int n)

{

if (n == 0)

return 1;

return n * factorial(n - 1);

}

int main()

{

int num = 5;

printf("Factorial of %d is %d",

num, factorial(num));

return 0;

}

Output

Factorial of 5 is 120

The Complexity of the Method

Time Complexity: O(n)

Auxiliary Space: O(n)

ii). Factorial Program Using Ternary Operator in C

C

#include <stdio.h>

int factorial(int n)

{

return ((n == 1 || n == 0) ? 1 : n * factorial(n - 1));

}

int main()

{

int num = 5;

printf("Factorial of %d is %d",

num, factorial(num));

return 0;

}

Output

Factorial of 5 is 120

The Complexity of the Method

Time Complexity: O(n)

Auxiliary Space: O(n)

3. Using tgamma() Method

The tgamma() method is a library function in math.h library in C programming language that computes the gamma function of the passed argument. Below is the C program to implement the approach:

C

#include <math.h>

#include <stdio.h>

int main()

{

int num = 5;

num = tgamma(num + 1);

printf("Factorial is %d", num);

return 0;

}

4. Using Pointers

Below is the C program to find the factorial of a number using Pointers:

C

#include <math.h>

#include <stdio.h>

int factorial(int n, int *fact)

{

int x;

*fact = 1;

for(x = 1; x <= n; x++)

*fact = *fact * x;

}

int main()

{

int fact;

int num = 5;

factorial(num, &fact);

printf("Factorial of %d is %d",

num, fact);

return 0;

}

Output

Factorial of 5 is 120

The Complexity of the Method

Time Complexity: O(n)

Auxiliary Space: O(1)

Last Updated :
22 May, 2023

Like Article

Save Article

Источник

Вычисление факториала

Вводится натуральное число. Вычислить его факториал.
Решение задачи на языке программирования Python

Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1 * 2 * 3 * 4 * 5 = 120.

Формула нахождения факториала:

n! = 1 * 2 * … * n,

где n – это число, а n! – факториал этого числа.

Формулу можно представить в таком виде:

n! = 1 * … * (n-2) * (n-1) * n,

т. е. каждый предыдущий множитель меньше на единицу, чем последующий. Или в перевернутом виде, когда каждый следующий меньше предыдущего на единицу:

n! = n * (n-1) * (n-2) * … * 1,

Для вычисления факториала с помощью цикла можно использовать любую формулу. Для рекурсивного вычисления используется вторая.

Вычисление факториала с помощью циклов

С помощь цикла while:

n = int(input())
 
factorial = 1
while n > 1:
    factorial *= n
    n -= 1
 
print(factorial)

Вычисление факториала с помощью цикла for:

n = int(input())
 
factorial = 1
 
for i in range(2, n+1):
    factorial *= i
 
print(factorial)

Нахождение факториала рекурсией

def fac(n):
    if n == 1:
        return 1
    return fac(n - 1) * n
 
 
print(fac(5))

Поток выполнения программы при n = 5:

Вызов функции fac(5)
fac(5) вызывает fac(4)
fac(4) вызывает fac(3)
fac(3) вызывает fac(2)
fac(2) вызывает fac(1)
fac(1) возвращает в fac(2) число 1
fac(2) возвращает в fac(3) число 1 * 2, т. е. 2
fac(3) возвращает в fac(4) число 2 * 3, т. е. 6
fac(4) возвращает в fac(5) число 6 * 4, т. е. 24
fac(5) возвращает число 24 * 5, т. е. 120 в основную ветку программы
Число 120 выводится на экран

Функция factorial модуля math

Модуль math языка программирования Python содержит функцию factorial, принимающую в качестве аргумента неотрицательное целое число и возвращающую факториал этого числа:

>>> import math
>>> math.factorial(4)
24

Больше задач в PDF

Источник

Время на прочтение
3 мин

Количество просмотров 8.1K

Самомодифицирующиеся программы воспринимаются как нечто магическое, но при этом они весьма просты, и чтобы это продемонстрировать, я напишу такую программу под x86 архитектуру в NASM.

Базовый факториал

Для начала нам понадобится обычная программа вычисления факториала.

factorial:
    push ebp
    mov ebx, eax
factorial_start:
    sub ebx, 1
    cmp ebx, 0
    je factorial_end
    mul ebx
    jmp factorial_start
factorial_end:
    pop ebp
    ret

Здесь все довольно просто.

Самомодифицирующийся факториал

В алгоритме вычисления факториала есть два места, в которых изменение значения при выполнении имеет смысл: начальное значение и множитель.

Технические особенности

Во-первых, самомодифицирующиеся программы имеют свою специфику. По умолчанию nasm собирает программу без возможности ее дальнейшей самостоятельной модификации, потому что раздел .text из соображений безопасности отмечается как не перезаписываемый. Чтобы изменить флаги этого раздела для активации возможности записи потребуется задействовать objcopy и кастомную программу.

Мой скрипт для сборки этих программ лежит здесь.

Начальное значение

В исходном коде начальное число передается через регистр eax. Чтобы использовать для этого самомодифицирующийся код, первым делом потребуется, чтобы в начале функции присутствовала обнуляющая инструкция mov для eax .

_start:
    mov dword [factorial+2], 0x5
    call factorial

factorial:
    push ebp
    mov eax, 0

Как видите, для передачи начального значения программа изменяет инструкцию mov eax. Значение 0 этой инструкции на 2 байта смещается от начала метода factorial.

Множитель

factorial_start:
    ; multiply
    mov ebx, 0
    mul ebx

Выше представлена заглушка, используемая для умножения. Далее нам нужна логика для установки mov ebx, 0, его декрементирования и выхода из цикла.

Инициализация множителя

Для установки множителя берем ebx, где хранится его первое значение, и копируем это значение в mov eax, 0 в начало метода factorial_start.

factorial:
    ...
    mov dword [factorial_start+1], ebx ; init decrementer

Декрементирование множителя

В стандартной программе логика будет такой:

декрементировать множитель;
если он окажется 0, выйти;
перепрыгнуть назад.

В нашей самомодифицирующейся программе изменяется единственная деталь – декрементирование множителя.

Для этого необходимо получить его текущее значение, уменьшить это значение и скопировать обратно.

factorial_start:
    ...
    ; decrement
    mov ebx, dword [factorial_start+1]
    sub ebx, 1
    mov dword [factorial_start+1], ebx

Результат

Совмещая все это, получаем:

extern printf

section .data
    format:    db "num: %d",10,0

section .text
	global _start

_start:
    mov dword [factorial+2], 0x5 ; start number
    
    call factorial
    ; print result
    push eax
    push format
    call printf
    ; exit
    mov eax, 1
	mov ebx, 0
    int 80h

factorial:
    push ebp
    mov eax, 0

    mov ebx, eax
    sub ebx, 1
    mov dword [factorial_start+1], ebx ; init decrementer
    mov ebx, 0

factorial_start:
    ; multiply
    mov ebx, 0
    mul ebx

    ; decrement
    mov ebx, dword [factorial_start+1]
    sub ebx, 1
    mov dword [factorial_start+1], ebx
    ; exit if at 0
    ; could exit at 1, but then it doesn't handle 0x2
    cmp ebx, 0
    je factorial_end
    ; loop back
    jmp factorial_start

factorial_end:
    pop ebp
    ret

Заключение

Я нахожу самомодифицирующиеся программы довольно интересными – их код выглядит несколько иначе, немного беспорядочен и содержит пустые значения, но при этом продумывать для них логику очень увлекательно.

Применяются они в различных областях, в основном относящихся к обфускации – к примеру, при реализации защиты лицензий или вредоносного ПО. Я подумываю создать на этом принципе собственный упаковщик или, по меньшей мере, прикольный crackme.

Если вам интересно познакомиться с другими примерами самомодифицирующихся программ под x86, то милости прошу в мой репозиторий.

Источник

На чтение 3 мин Просмотров 4.5к. Опубликовано 28.02.2023

Содержание

Введение
Вычисление факториала циклом while
Цикл while
Цикл for
Вычисление факториала Рекурсией
Вычисление факториала методом factorial()
Заключение

Введение

В ходе статьи рассмотрим 3 способа вычислить факториал в Python.

Вычисление факториала циклом while

Цикл while

Для начала дадим пользователю возможность ввода числа и создадим переменную factorial равную единице:

number = int(input('Введите число: '))
factorial = 1

Как мы знаем, факториал – это произведение натуральных чисел от единицы до числа n. Следовательно создадим цикл, который не закончится, пока введённое пользователем число больше единицы. Внутри цикла увеличиваем значение в переменной factorial умножая его на переменную number, после чего уменьшаем значение в number на единицу:

number = int(input('Введите число: '))
factorial = 1

while number > 1:
    factorial = factorial * number
    number = number - 1

print(factorial)

# Введите число: 10
# 3628800

Цикл for

Обычно способ нахождения факториала при помощи цикла for не рассматривается, но почему бы и нет. Принцип не сильно отличается от цикла while, просто приравниваем значение введённое пользователем к переменной factorial, а в цикле указываем количество итреаций начиная с единицы, и заканчивая введённым числом:

number = int(input('Введите число: '))
factorial = number

for i in range(1, number):
    factorial = factorial * i

print(factorial)

# Введите число: 5
# 120

Вычисление факториала Рекурсией

Для вычисления факториала про помощи рекурсии, создадим функцию factorial(), и в качестве аргумента передадим number:

Внутри функции добавим условие, что если переданное число в аргумент number равняется единице, то возвращаем его. Если же условие не сработало, то вернётся аргумент number умноженный на вызов функции factorial() с передачей аргумента number – 1:

def factorial(number):
    if number == 1:
        return number
    else:
        return number * factorial(number - 1)

Дадим пользователю возможность ввода, вызовем функцию и выведем результат в консоль:

def factorial(number):
    if number == 1:
        return number
    else:
        return number * factorial(number - 1)


print(factorial(int(input('Введите число: '))))

# Введите число: 7
# 5040

Вычисление факториала методом factorial()

В стандартном модуле math есть специальный метод для вычисления факториала под названием factorial(). Используем его для нахождения факториала:

from math import factorial

number = int(input('Введите число: '))

print(factorial(number))

# Введите число: 4
# 24

Заключение

В ходе статьи мы с Вами рассмотрели целых 3 способа вычислить факториал в Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂

Admin

Источник