Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Кратный факториал. Некоторые моменты. / 20 сообщений из 20, страница 1 из 1
22.08.2014, 03:38
    #38726184
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Здравствуйте.

Сегодня, я был очень удивлён. Потому, у меня такой вопрос. Представьте что вам нужно написать простейшую функцию кратного факториала. Она ниже, но без указания типов данных. Пусть, T_i либо unsigned, либо int.

Вообще говоря, входные параметры всегда больше нуля. И выход также всегда больше нуля. Подскажите пожалуйста, как бы вы расставили типы данных в коде ниже ?


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
T0 mul_fac(T1 n, T2 k)
{
	T3 res = 1;
	for (T4 i = n; i >= n%k && i != 0; i -= k)
	{
		res *= i;
	}
	return res;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 09:46
    #38726286
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
SashaMercury,

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
unsigned int mul_fac(unsigned int n, unsigned int k)
{
	unsigned int res = 1;
	for (unsigned int i = n; i + k >= k; i -= k)
	{
		res *= i;
	}
	return res;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 09:56
    #38726296
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
хотя это некорректно, т.к. нужно обработать случаи n=k и n<k.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:01
    #38726307
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
На всякий случай привожу ссылку (для мемберов).

https://ru.wikipedia.org/wiki/Факториал#.D0.9A.D1.80.D0.B0.D1.82.D0.BD.D1.8B.D0.B9_.D1.84.D0.B0.D0.BA.D1.82.D0.BE.D1.80.D0.B8.D0.B0.D0.BB
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:10
    #38726312
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Учитывай что у данных типов переполнение никак не обрабатывается, а при вычислении факториалов можно легко выйти за 2^32.
Поэтому лучше знаковый int и проверку что res > 0.
Код: plaintext
1.
2.
3.
4.
5.
6.
	int res = 1;
	for (T4 i = n; i >= n%k && i != 0; i -= k)
	{
		res *= i;
		if(res <= 0) printf("переполнение");
	}



По возможности надо проверять что значения не уходят за допустимые параметры. Иначе получишь 100% гарантию в какой-то момент получить неверный результат и не будешь знать что он неверный.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:10
    #38726313
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
mayton,

т.е. результат не определён для n, не кратного k?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:20
    #38726323
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
RWolf , спасибо. Но ваш алгоритм не верен. Например, в классическом случае, при кратности 1, 3!=0, согласно вашему предложению.

Однако, дело не в этом. Я тоже поставил unsigned везде, и вероятно для всех вас очевидно, но я так и не понял почему этот код уходит в бесконечный цикл, если на входе например 10,3

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
unsigned int mul_fac(unsigned n, unsigned k)
{
	unsigned res = 1;
	for (int i = n; i >= n%k && i != 0; i -= k)
	{
		res *= i;
	}
	return res;
}



А вот такой код, например, работать будет

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
unsigned int mul_fac(int n, int k)
{
	unsigned res = 1;
	for (int i = n; i >= n%k && i != 0; i -= k)
	{
		res *= i;
	}
	return res;
}




Я думаю, что дело в выражении
Код: plaintext
1.
i >= n%k



но я сохранял остаток от деления в отдельную переменную типа int, и результат был прежним. А сейчас снова проверил, и всё нормально заработало. Т.е. скорее всего проблема с типами данных.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:21
    #38726326
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Ух ты, я пока писал ответ, тут ещё столько сообщений появилось C:
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:23
    #38726330
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
SashaMercury,

да, неверно — я не сделал проверку на ноль:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
unsigned int mul_fac(unsigned int n, unsigned int k)
{
	unsigned int res = 1;
	for (unsigned int i = n; i + k >= k && i != 0; i -= k)
	{
		res *= i;
	}
	return res;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:23
    #38726332
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Дмитрий,
в моём случае 1<=n<=10, потому по поводу переполнения я не волновался.
Нужно было сразу про это написать
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:36
    #38726340
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
SashaMercury Я тоже поставил unsigned везде, и вероятно для всех вас очевидно, но я так и не понял почему этот код уходит в бесконечный цикл, если на входе например 10,3

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
unsigned int mul_fac(unsigned n, unsigned k)
{
	unsigned res = 1;
	for (int i = n; i >= n%k && i != 0; i -= k)
	{
		res *= i;
	}
	return res;
}


Не везде поставил. Похоже срабатывает неявное приведение типов.
SashaMercuryв моём случае 1<=n<=10, потому по поводу переполнения я не волновался.
тогда бери int, с ним удобнее и компилятор не будет ворнинги писать про сравнения знаковых и беззнаковых и т.п.

кстати цикл проще так написать
Код: plaintext
1.
for (int i = n; i > 0; i -= k)


думаю так оба варианта заработают
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:53
    #38726363
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Я бы посоветовал везде где возможно использовать int, т.к. он более универсальный.
unsigned int в исключительных случаях, например для хранения флагов, или когда изначально задано что значение в диапазоне 0 - 2^32-1, например CRC32.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 10:59
    #38726374
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
SashaMercuryя так и не понял почему этот код уходит в бесконечный цикл, если на входе например 10,3


При сравнении знакового и беззнакового оба операнда рассматриваются как беззнаковые. Когда i станет отрицательным, условие выхода не сработает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 12:23
    #38726507
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Ребята. Факториал это очень быстро растущая функция. Факториал 13 уже превышает сетку int32.

Здесь как раз нужна арифметика символьных вычислений.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 13:31
    #38726634
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
SashaMercury
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
T0 mul_fac(T1 n, T2 k)
{
        ASSERT(n>0, "N less than 0, you stuped codemonkey!");
        ASSERT(k>0, "K less than 0, you stuped idiot! Get out!");
	T3 res = 1;
	for (T4 i = n; i >= n%k && i != 0; i -= k)
	{
		res *= i;
	}
	return res;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 15:35
    #38726829
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Ребята, вы не поверите !
Сейчас шел по темным улицам из магазина, и 1. понял в чём ошибка, 2. В чём была бы ошибка, если бы я был прав изначально 3. Появился ещё один вопрос

Только переоденусь и напишу, с расстановкой

весёлые комментарии :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 16:19
    #38726915
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
А нет. Я не ошибся. Думал что логическая ошибка, но всё нормально.
Пока шел вспомнил то, про что написал RWolf, глава 2 K&R, если в выражении присутствует unsigned, то всё приводится к этому типу. Вроде бы так. Вероятно по этому и происходит.

Дмитрий, ваш вариант лучше того что я написал. Но с unsigned почему-то не срабатывает. Почему сейчас то не срабатывает? А видимо по этой же причине. Появляется битовая единица в старшем разряде(когда уходим в минус), но так unsigned читается как 2^31,а не как -1.

Вообще совет с int вероятно буду использовать. Не "вероятно", а буду.

mayton, вы правы, длинная арифметика в общем случае нужна, но в данном случае нет, я тестировал кое-что..

Вот казалось бы, столько читаю,программирую, а всё-равно детские ошибки. И ведь вспомнил про приведение к unsigned, правда вечером, но сам вспомнил. Но почему сразу не понял этого ((( Должен был сразу увидеть это(


Всем спасибо :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 16:20
    #38726918
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
Саша я вот щас шёл по коридорам офиса, зашёл в кофе-автомат и вот думал
что ты наверное всё уже знаешь по С/C++ а вопросы задаёшь просто так
по приколу. Может твоя фамилия Луговский и ты решил нас всех круто
развести.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 16:31
    #38726930
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
ахаха, нет конечно, я точно не он
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.08.2014, 20:57
    #38727127
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Кратный факториал. Некоторые моменты.
SashaMercuryВот казалось бы, столько читаю,программирую, а всё-равно детские ошибки.
Это нормально. Лично я "детские" ошибки перестал делать лет через десять после начала работы программистом. Тут главное понять почему наступил на грабли и принять меры чтобы это не повторить.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Кратный факториал. Некоторые моменты. / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]