Факториал в C без условных выражений, циклов и арифметических операторов
https://stackoverflow.com/questions/653961
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как я могу найти факториал числа (от 1 до 10) в C, не используя:
- операторы цикла, такие как for, while и do while;
- условные операторы , такие как if и case;и
- арифметические операторы , такие как + , − , * , % , /, ++, --?
К ТВОЕМУ СВЕДЕНИЮ:Я нашел этот вопрос в C aptitude.
Решение
Поскольку это всего лишь от 1 до 10, просто предварительно вычислите его и сохраните в простом массиве int размером 11.Для первого элемента в массиве поставьте 1.Это недопустимый диапазон входных данных для вашей проблемы, но с таким же успехом он может быть правильным.
Нам нужно сохранить 11 элементов вместо 10, которые нам нужны, потому что в противном случае нам пришлось бы использовать операцию "-", чтобы получить правильный индекс.Однако в вашей задаче вычитание не разрешено.
int factorial(int x)
{
return precomputedArray[x];
}
Другие советы
Вот решение без циклов, арифметики или условных выражений, которое не прибегает к предварительному вычислению. Он также не использует условия короткого замыкания, такие как && или || которые на практике эквивалентны if. Таким образом, это, по-видимому, первое правильное решение вообще без каких-либо условий.Теперь на правильном C без функций C ++ :)
#include <stdio.h>
#define uint unsigned int
void A(uint *a, uint *b)
{
uint tmp = *a & *b;
*a = (*a | *b) & ~tmp;
*b = tmp << 1;
}
#define REPEAT32(s) \
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
uint add(uint a, uint b)
{
REPEAT32(A(&a, &b);) return a;
}
uint bitexpand(uint b)
{
b = (b << 1) | b; b = (b << 2) | b; b = (b << 4) | b;
b = (b << 8) | b; b = (b << 16) | b;
return b;
}
void M(uint *acc, uint *a, uint *b)
{
*acc = add(*acc, *a & bitexpand(*b & 1));
*a <<= 1;
*b >>= 1;
}
uint mult(uint a, uint b)
{
uint acc = 0;
REPEAT32(M(&acc, &a, &b);) return acc;
}
uint factorial(int n)
{
uint k = 1;
uint result = 0;
result |= (bitexpand(n == 1) & k);
k = mult(k, 2); result |= (bitexpand(n == 2) & k);
k = mult(k, 3); result |= (bitexpand(n == 3) & k);
k = mult(k, 4); result |= (bitexpand(n == 4) & k);
k = mult(k, 5); result |= (bitexpand(n == 5) & k);
k = mult(k, 6); result |= (bitexpand(n == 6) & k);
k = mult(k, 7); result |= (bitexpand(n == 7) & k);
k = mult(k, 8); result |= (bitexpand(n == 8) & k);
k = mult(k, 9); result |= (bitexpand(n == 9) & k);
k = mult(k, 10); result |= (bitexpand(n == 10) & k);
return result;
}
int main(int argc, char **argv)
{
uint i;
/* Demonstration loop, not part of solution */
for (i = 1; i <= 10; i++)
{
printf("%d %d\n", i, factorial(i));
}
}
Обновленный:обсуждение содержало утверждение о том, что короткое замыкание условного типа && было бы приемлемо в решении, которое не использует if.Вот простой макрос, который имитирует двустороннее 'if' с использованием && и, очевидно, делает всю проблему намного менее интересной:
#define IF(i, t, e) \
(void)((i) && (goto then##__LINE__, 1)); goto else##__LINE__;
then##__LINE__: t; goto cont##__LINE__; \
else##__LINE__: e; cont##__LINE__: ((void)0);
Затем вы можете определить
#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))
и тогда остальная часть проблемы становится тривиальной.
#include <stdio.h>
static const int factorial[] = {
1,
1,
2,
6,
24,
120,
720,
5040,
40320,
362880,
3628800,
};
/* Test/demo program. */
int main(void)
{
int i;
for (i = 0; i <= 10; ++i)
printf("%d %d\n", i, factorial[i]);
return 0;
}
(Любой, кто использует этот ответ для домашнего задания, либо терпит неудачу, либо у него есть учитель с хорошим чувством юмора.)
(Ба, я был медлительным.Другие люди уже давали этот ответ.Не стесняйтесь голосовать за них отвечайте.)
Может быть, я решаю чью-то домашнюю работу, но это выглядело как забавная задача, в любом случае, вот мое решение (компилируется с предупреждениями, но не могу помочь им, не делая это некрасивым (э))
Редактировать: Я изменил программу, чтобы она поддерживала значительно более длинные факториалы (до 20 или около того), и сделал код немного аккуратнее, удалив таблицу подстановки внутри prev().
#include <stdio.h>
#include <stdlib.h>
#define _if(CND, OP1, OP2) (((CND) && ((OP1) || 1)) || (OP2))
long long int add(long long int x, long long int y){
long long int r = x ^ y;
long long int c = x & y;
c = c << 1;
_if(c != 0, r = add(r, c), 1);
return r;
}
long long int prev(long long int x){
return add(x, -1);
}
long long int mult(long long int x, long long int y){
long long int r;
_if(x == 0,
r = 0,
_if(x == 1,
r = y,
r = add(y, mult(prev(x), y))));
return r;
}
long long int fac(long long int x){
long long int r;
_if(x < 2,
r = 1,
r = mult(x, fac(prev(x))));
return r;
}
int main(int argc, char**argv){
long long int i;
for(i = 0; i <= 20; i++)
printf("factorial(%lli) => %lli\n", i, fac(i));
return 0;
}
Пробный запуск:
[dsm@localhost:~/code/c]$ gcc -o proc proc.c
[dsm@localhost:~/code/c]$ ./proc #/
factorial(0) => 1
factorial(1) => 1
factorial(2) => 2
factorial(3) => 6
factorial(4) => 24
factorial(5) => 120
factorial(6) => 720
factorial(7) => 5040
factorial(8) => 40320
factorial(9) => 362880
factorial(10) => 3628800
factorial(11) => 39916800
factorial(12) => 479001600
factorial(13) => 6227020800
factorial(14) => 87178291200
factorial(15) => 1307674368000
factorial(16) => 20922789888000
factorial(17) => 355687428096000
factorial(18) => 6402373705728000
factorial(19) => 121645100408832000
factorial(20) => 2432902008176640000
[dsm@localhost:~/code/c]$
"+", "-" и "* " явно запрещены, но "+=", "-=" и "*=" - нет, и поэтому рекурсивная реализация становится…
int factorial( int arg )
{
int argcopy = arg;
argcopy -= 1;
return arg == 1 ? arg : arg *= factorial( argcopy );
}
VC7 отказывается компилировать вышеупомянутое, когда находится в режиме "compile as C source" – жалуется на постоянное L-значение для "*=", но вот другой вариант того же самого:
int factorial( int arg )
{
int argcopy1 = arg;
int argcopy2 = arg;
argcopy1 -= 1;
argcopy2 *= arg == 1 ? 1 : fact( argcopy1 );
return argcopy2;
}
Это не полный ответ, а просто разные подходы к add() и mult() функции:
#define add(a, b) sizeof (struct { char x[a]; char y[b]; })
#define mult(a, b) sizeof (struct { char x[a][b]; })
(Я считаю, что C, в отличие от C ++, допускает определение новых типов внутри sizeof.)
Вот еще одна (полностью непереносимая) реализация add() на основе арифметики указателей:
int add(int x, int y) {
return (int) &((char*) x)[y];
}
Вот решение (the Только пока один), который фактически решает проблему при требуемых ограничениях.
int fac( int n )
{
/* The is the binary representation of the function: */
/* 0000 => 0000000000000000001 */
/* 0001 => 0000000000000000001 */
/* 0010 => 0000000000000000010 */
/* 0011 => 0000000000000000110 */
/* 0100 => 0000000000000011000 */
/* 0101 => 0000000000001111000 */
/* 0110 => 0000000001011010000 */
/* 0111 => 0000001001110110000 */
/* 1000 => 0001001110110000000 */
/* 1001 => 1011000100110000000 */
int bit0 = n & 1;
int bit1 = (n & 2) >> 1;
int bit2 = (n & 4) >> 2;
int bit3 = (n & 8) >> 3;
int notbit0 = bit0 ^ 1;
int notbit1 = bit1 ^ 1;
int notbit2 = bit2 ^ 1;
int notbit3 = bit3 ^ 1;
return
(bit0 & notbit1 & notbit2 & bit3) << 18 |
(bit0 & notbit1 & notbit2 & bit3) << 16 |
(notbit1 & notbit2 & bit3) << 15 |
(notbit1 & notbit2 & bit3) << 11 |
(notbit1 & notbit2 & bit3) << 8 |
(notbit1 & notbit2 & bit3) << 7 |
(notbit0 & notbit1 & notbit2 & bit3) << 12 |
(notbit0 & notbit1 & notbit2 & bit3) << 10 |
(bit0 & bit1 & bit2 & notbit3) << 12 |
(bit1 & bit2 & notbit3) << 9 |
(bit0 & bit1 & bit2 & notbit3) << 8 |
(bit1 & bit2 & notbit3) << 7 |
(bit0 & bit2 & notbit3) << 5 |
(bit2 & notbit3) << 4 |
(notbit0 & bit1 & bit2 & notbit3) << 6 |
(bit0 & notbit1 & bit2 & notbit3) << 6 |
(notbit1 & bit2 & notbit3) << 3 |
(bit0 & bit1 & notbit2 & notbit3) << 2 |
(bit1 & notbit2 & notbit3) << 1 |
(notbit1 & notbit2 & notbit3);
}
Вот тестовая программа:
#include <stdio.h>
int main()
{
int i, expected, j;
for( i = 0; i < 10; ++i )
{
expected = 1;
for( j = 2; j <= i; ++j )
{
expected *= j;
}
if( expected != fac( i ) )
{
printf( "FAILED: fac(%d) = %d, expected %d\n", i, fac( i ), expected );
}
}
}
Использование asm написать ассемблерный код.
Или предварительно скомпилируйте программу и запустите ее из своей программы.
Зачем вам налагать такие ограничения на свой код?
вот решение, которое использует арифметику указателей для арифметики и указатели функций для условных выражений.
#include <stdio.h>
int fact(int n);
int mul(int a, int b)
{
struct s {
char _v[b];
};
struct s *p = (struct s*)0;
return (int) &p[a];
}
int add(int a, int b)
{
return (int) (&((char *)a)[b]);
}
int is_0(int n)
{
return (n == 0);
}
int fact_0(int n)
{
return 1;
}
int fact_n(int n)
{
return mul(n, fact(add(n,-1)));
}
int (*facts[2])(int) = {fact_n, fact_0};
int fact(int n)
{
return facts[is_0(n)](n);
}
int main(int argc, char **argv)
{
int i;
for(i = 0; i<=10; i++) {
printf("fact %d = %d\n", i, fact(i));
}
}
Пробный запуск:
~ > gcc -std=c99 fact.c
~ > ./a.out
fact 0 = 1
fact 1 = 1
fact 2 = 2
fact 3 = 6
fact 4 = 24
fact 5 = 120
fact 6 = 720
fact 7 = 5040
fact 8 = 40320
fact 9 = 362880
fact 10 = 3628800
Создайте гигантский набор троичных операторов, возвращающих предварительно вычисленное значение для каждого разрешенного ввода.Используйте макросы для вычисления значений.
Вычисление факториала - это первый (и для многих людей последний) раз, когда вы используете рекурсию.Стандартной реализацией является
long fact(int x)
{
if (x < 2)
return 1L;
else
return fact(x - 1) * x;
}
Некоторые утверждают, что это последнее утверждение должно быть "x * fact(x-1)", чтобы компилятор мог распознать, что это хвостовая рекурсия.Лично я сомневаюсь, что какой-либо компилятор достаточно умен, чтобы видеть его в этой форме и не видеть в другой форме.
Однако, поскольку вы запретили использовать "если" или "-", я не знаю, как бы вы это сделали.
черновой набросок (уже предложен другими!)
int[] factorials = {1,1,2,6,24, 120,720, ..etc };
return factorials[i];
я тоже попытался, поместив значения в массив.здесь я использовал условия if и циклы while, но никаких арифметических операторов не задействовал.!пытаюсь, смогу ли я удалить и их тоже.
#include <stdio.h>
int add(int a, int b)
{
int t1, t2, ab, bb, cb=0, orb=1, ans=0;
do {
t1 = a >> 1;
t2 = t1 << 1;
if (a==t2) ab=0; else ab=1;
t1 = b >> 1;
t2 = t1 << 1;
if (b==t2) bb=0; else bb=1;
if (ab==1 && bb==1) {
if (cb==1) ans=ans | orb;
cb = 1;
}
if ( ab!=bb ) {
if (cb==0) ans = ans | orb;
}
if (ab==0 && bb==0) {
if (cb==1) {
ans = ans | orb;
cb=0;
}
}
orb = orb << 1;
a = a >> 1;
b = b >> 1;
} while (a!=0 || b!=0);
if (cb==1) ans = ans | orb;
return ans;
}
int multiply(int x,int y)
{
int result = 0, i = 0 , j=0;
while((i=add(i,1)) <= y)
result = add(result,x);
return result;
}
int factorial(int x)
{
if(x==1)
return 1;
else
return multiply(x,factorial(x-1));
}
int main()
{
int x;
printf("Enter a number between 0 and 10: ");
scanf("%d" , &x);
printf("\nFactorial: %d\n" , factorial(x));
return 0;
}
Давайте посмотрим, сможем ли мы сделать что-то наполовину элегантное, не завися от 1 <= n <= 10.
- Вместо зацикливания мы, конечно, будем использовать рекурсию.
- Вместо if для завершения рекурсии мы будем использовать массив указателей на функции!
(Нам все еще нужны операторы сравнения, такие как<и==.)
Редактировать: дамару сначала использовал трюк с указателями на функции.
Это дает:[Весь код непроверен, под рукой нет компилятора C!]
typedef int (*unary_fptr)(int);
int ret_1(int n) {
return 1;
}
int fact(int n) {
unary_fptr ret_1_or_fact[] = {ret_1, fact};
return multiply(ret_1_or_fact[n > 1](sub_1(n)), n);
}
Нам все еще нужно внедрить sub_1 и multiply.Давайте начнем с sub_1, который представляет собой простую рекурсию по битам до тех пор, пока перенос не прекратится (если вы этого не понимаете, аналогичный add_1 в конце проще подумать об этом):
int identity(int n) {
return n;
}
int sub_1(int n) {
unary_fptr sub_1_or_identity[] = {sub_1, identity};
int lsb = n & 1;
int rest = sub_1_or_identity[lsb](n >> 1);
return (rest << 1) | (lsb ^ 1);
}
multiply:Самое простое, что я могу придумать, это Русское крестьянское умножение, что сводит его к двоичным сдвигам и сложению.С условными выражениями рекурсивная формулировка выглядела бы следующим образом:
/* If we could use conditionals */
int multiply(int a, int b) {
int subproduct;
if(a <= 1) {
subproduct = 0;
} else {
subproduct = multiply(a >> 1, b << 1);
}
if(a & 1) {
return add(b, subproduct);
} else {
return subproduct;
}
}
Без условных выражений нам приходится дважды использовать трюк с массивом отправки:
typedef int (*binary_fptr)(int, int);
int ret_0(int a, int b) {
return 0;
}
int multiply(int a, int b) {
binary_fptr ret_0_or_multiply = {ret_0, multiply};
int subproduct = ret_0_or_multiply[a >= 2](a >> 1, b << 1);
binary_fptr ret_0_or_add = {ret_0, add};
return ret_0_or_add[a & 1](subproduct, b);
}
Теперь все, чего нам не хватает, это add.Вы уже должны догадаться, как это будет происходить - одновременная рекурсия по битам двух чисел, что сводит проблему к сдвигам и add_1:
int add(int a, int b) {
int lsb = (a & 1) ^ (b & 1);
int carry = (a & 1) & (b & 1);
binary_fptr ret_0_or_add = {ret_0, add};
int subsum = ret_0_or_add[(a >= 2) & (b >= 2)](a >> 1, b>> 1);
unary_fptr identity_or_add_1 = {identity, add_1};
return identity_or_add_1[carry](subsum << 1);
}
и add_1 это простая рекурсия по битам до тех пор, пока перенос не прекратится:
int add_1(int n) {
unary_fptr identity_or_add_1[] = {identity, add_1};
int lsb = n & 1;
int rest = identity_or_add_1[lsb](n >> 1);
return (rest << 1) | (lsb ^ 1);
}
Вот и все, я думаю![Как отмечалось выше, весь код непроверен!]
Если вы не можете использовать рекурсию или арифметику и у вас ограниченный диапазон входных данных, вы могли бы жестко запрограммировать результат в виде поиска по массиву,
итак:
return factorials[x];
где вы предварительно заполнили factorials с соответствующими значениями
что делать, если нам нужно вычислить факториалы от 1 до 100.Как хранить эти большие числа?
#include<stdio.h>
void main()
{
unsigned long int num,fact,counter;
while(counter<=num)
{
printf("Enter the number");
scanf("%d",&num);
fact=fact*counter;
counter++;
printf("The factorial of number entered is %lu",fact);
}
printf("press any key to exit...");
getch();
}
Поскольку в нем не говорилось не использовать библиотечные функции:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int main( int argc, char** argv)
{
printf( "%d\n", (int)round( exp( lgamma(2))));
printf( "%d\n", (int)round( exp( lgamma(3))));
printf( "%d\n", (int)round( exp( lgamma(4))));
printf( "%d\n", (int)round( exp( lgamma(5))));
printf( "%d\n", (int)round( exp( lgamma(6))));
printf( "%d\n", (int)round( exp( lgamma(7))));
printf( "%d\n", (int)round( exp( lgamma(8))));
printf( "%d\n", (int)round( exp( lgamma(9))));
printf( "%d\n", (int)round( exp( lgamma(10))));
printf( "%d\n", (int)round( exp( lgamma(11))));
return 0;
}
