| Вопрос: Любопытная задачка | Добавлено: 22.01.05 22:22 |
Автор вопроса:  Sharp | Web-сайт: sharpc.livejournal.com | ICQ: 216865379 |
|
По заданному N найти все уникальные наборы чисел a[1..N] такие, что 1/a[1] + 1/a[2] + ... + 1/a[N] = 1. Перестановки не учитывать.
Пример: N=3 2 3 6 2 4 4 3 3 3 Еще один вопрос, больше теоретический. Предполагая, что ни одно число не выходит за границы типа Long, определить накладываемый этим условием предел на N. |
| Ответы | Всего ответов: 9 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 23.01.05 17:19 |
|
Ну вот, я думал, хоть кто-нибудь решит... Вот мое решение:
/*
По заданному N найти все уникальные наборы чисел a[1..N] такие, что 1/a[1] + 1/a[2] + ... + 1/a[N] = 1. Перестановки не учитывать. 20 января 2005 года © Остапенко Денис */ #include "stdio.h" int res[20][10000], lp=0, n; void simplize(int *nom, int *den){ int t1 = *nom, t2 = *den, t; while(t1%t2){ t1 = t1%t2; t = t1; t1 = t2; t2 = t; } *nom /= t2; *den /= t2; } void calc(int nom, int den, int ns){ int i; if(ns == 1){ if(nom ==1){ res[n-ns][lp] = den; lp++; for(i=0; i<n; i++) res[lp] = res[lp-1]; } return; } else{ i=n-ns?res[n-ns-1][lp]:2; while(den >= nom*i) i++; while(ns*den >= i*nom){ res[n-ns][lp] = i; int nnom, nden; nnom = nom*i - den; nden = den * i; simplize(&nnom, &nden); calc(nnom, nden, ns-1); i++; } } } int checkdouble(){ int u=1, i, j, k; for(k=0; k<n; k++) printf("%d\t", res[k][0]); printf("\n"  ;
for(i=1; i<lp; i++){ for(j=0; j<n; j++){ if(res[j] != res[j][i-1]) break; } if(j < n){ for(k=0; k<n; k++) printf("%d\t", res[k]); printf("\n" ;
u++; } } return u; } void main(){ printf("Enter N: " ;
scanf("%d", &n); calc(1, 1, n); printf("%d\n", checkdouble()); } Максимальное N = 6. |
||
|
Номер ответа: 2 Автор ответа: sneРазработчик Offline Client ICQ: 233286456 Вопросов: 34 Ответов: 5445 |
Web-сайт: Профиль | | #2 | Добавлено: 23.01.05 21:52 |
Че-то длинно  Я уже решал, у мня короче кажись... тоже писал на Си, но исходника найти не смог 
|
||
|
Номер ответа: 3 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #3 | Добавлено: 23.01.05 22:32 |
|
Ну, можно провести хакеризацию этого кода, он станет раза в 4 меньше
|
||
|
Номер ответа: 4 Автор ответа: sneРазработчик Offline Client ICQ: 233286456 Вопросов: 34 Ответов: 5445 |
Web-сайт: Профиль | | #4 | Добавлено: 24.01.05 01:32 |
|
) во, что-то похожее на дело )
Кстати, есть индивидумы, по-крайней мере у нас в группе таковые существовали, что все писали в одну единственную строчку
Мне бывало жаль нашего преподователя
|
||
|
Номер ответа: 5 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #5 | Добавлено: 24.01.05 02:08 |
|
Глянь сюда: www.ioccc.org
|
||
|
Номер ответа: 6 Автор ответа: sneРазработчик Offline Client ICQ: 233286456 Вопросов: 34 Ответов: 5445 |
Web-сайт: Профиль | | #6 | Добавлено: 24.01.05 10:45 |
|
Нащ препор после многолетних тренировок любой (почти) обфускатор опустит с таким-то опытом
|
||
|
Номер ответа: 7 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #7 | Добавлено: 24.01.05 12:50 |
| Маза собрать воедино все известные методы обфускации исходного кода на всех языках и выпустить, как шутливую статью "Как нужно писать программы". | ||
|
Номер ответа: 8 Автор ответа: sneРазработчик Offline Client ICQ: 233286456 Вопросов: 34 Ответов: 5445 |
Web-сайт: Профиль | | #8 | Добавлено: 24.01.05 15:33 |
|
) Это как был прикол про то как придумали синтаксис Си языка
|
||
|
Номер ответа: 9 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #9 | Добавлено: 25.01.05 00:43 |
| Да, наслышан, хотя на самом деле история куда более прозаическая | ||
Страница: 1 |