ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Кратный факториал. Некоторые моменты.
20 сообщений из 20, страница 1 из 1
Кратный факториал. Некоторые моменты.
    #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, 03:38
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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:46
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #38726296
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RWolf
Участник
хотя это некорректно, т.к. нужно обработать случаи n=k и n<k.
...
Рейтинг: 0 / 0
22.08.2014, 09:56
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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:01
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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:10
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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:20
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #38726326
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Ух ты, я пока писал ответ, тут ещё столько сообщений появилось C:
...
Рейтинг: 0 / 0
22.08.2014, 10:21
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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:23
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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:36
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #38726363
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я бы посоветовал везде где возможно использовать int, т.к. он более универсальный.
unsigned int в исключительных случаях, например для хранения флагов, или когда изначально задано что значение в диапазоне 0 - 2^32-1, например CRC32.
...
Рейтинг: 0 / 0
22.08.2014, 10:53
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #38726374
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RWolf
Участник
SashaMercuryя так и не понял почему этот код уходит в бесконечный цикл, если на входе например 10,3


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

Здесь как раз нужна арифметика символьных вычислений.
...
Рейтинг: 0 / 0
22.08.2014, 12:23
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #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, 13:31
| Ответить | Цитировать | Написать  
Кратный факториал. Некоторые моменты.
    #38726829
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Ребята, вы не поверите !
Сейчас шел по темным улицам из магазина, и 1. понял в чём ошибка, 2. В чём была бы ошибка, если бы я был прав изначально 3. Появился ещё один вопрос

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

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

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

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

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

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


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


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