Форум на Исходниках.RU

Задача №4

experimenter — Wed, 07 Apr 2004 08:01:40 +0000

experimenter: 2 Sazabis
так и нигде и не пересоздавал массив. там же везде ссылка стоит. а память, там сроду не должна была кроме одного раза как максимум перераспределиться.

Задача №4

Sazabis — Wed, 07 Apr 2004 06:58:59 +0000

Sazabis:

Цитата

experimenter, 7.04.04, 09:09
здорово, конечно. а потом говорят, что ООП программирование такое же эффективное, как и процедурное.

Я бы не стал так расстраиваться ;) в конце концов в std, привиденных, вариантах
( experimenter и flex ferrum ) не было использовано то, что массив нет необходимости пересоздовать!, достаточно ограничивать вывод элементов массива :yes:

Цитата

trainer, 7.04.04, 09:41
P.S. Я так понимаю, народ понемногу созревает к соревнованиям на скорость.

e-e! it's cool :yes:

Задача №4

SVK — Wed, 07 Apr 2004 06:48:54 +0000

SVK :

Цитата trainer,7.04.04, 09:21

Придумай задачу - будем решать. :)

Есть четырёхсвязный список элементов, т.е. в полной укомплектации это решетка .
Задача: без использования рекурсии, расцепить все дочерние-нижестоящие элементы, начиная с указанного; без привлечения каких-либо дополнительных ресурсов, но элемент может содержать служебные поля (заполняемые в процессе разцепления и/или формирования). ЯВУ реализации - СИ.
Примечание: можно принять допущение, что полной решетки быть не может, т.е. без циклов.

Задача №4

trainer — Wed, 07 Apr 2004 06:41:16 +0000

trainer: P.S. Я так понимаю, народ понемногу созревает к соревнованиям на скорость. :)

Задача №4

tserega — Wed, 07 Apr 2004 06:36:10 +0000

tserega: Мне тоже понравилось! Случайно заметил эту тему, решил поучаствовать. Жду следующую!!!

Задача №4

trainer — Wed, 07 Apr 2004 06:21:32 +0000

trainer:

Цитата

experimenter, 7.04.04, 09:09
когда планируется следующая задачка?

На днях. :)

Цитата

experimenter, 7.04.04, 09:09
еще у меня что-то типа пожелания.
эта задачка очень похожа на переборную и вместо вывода на экран лучше искать какой-то минимум на всей области решений или что-то типа того, тогда легче оценивать время.

Придумай задачу - будем решать. :)

Задача №4

experimenter — Wed, 07 Apr 2004 06:09:10 +0000

experimenter: здорово, конечно. а потом говорят, что ООП программирование такое же эффективное, как и процедурное.
кстати, когда следующая задача планируется? мне очень нравится все, но какая конечная цель?
еще у меня что-то типа пожелания.
эта задачка очень похожа на переборную и вместо вывода на экран лучше искать какой-то минимум на всей области решений или что-то типа того, тогда легче оценивать время.
когда планируется следующая задачка? :)

Задача №4

tserega — Tue, 06 Apr 2004 14:32:58 +0000

tserega: Вау! Вот это комментарии и исследование!!!

Задача №4

Sazabis — Tue, 06 Apr 2004 13:11:46 +0000

Sazabis: Итак, несколько слов о задаче:

в общем все уже поняли алгоритм, дающий только нужные варианты, приведу свой код

void Analyze( unsigned rest, unsigned step, unsigned *prefix, unsigned prefix_size ){

// Вывод

if( !rest && prefix_size > 1 ){

for( unsigned i=0;i<prefix_size-1;i++ )cout<< prefix[ i ] << '+';

cout<< prefix[ prefix_size-1 ] << endl;

return;

}

// Итерации

for( unsigned i=rest < step ? rest : step;i;--i ){

prefix[ prefix_size ] = i;

Analyze( rest - i, i, prefix, prefix_size + 1 );

}

в, общем, логика у всех одинаковая, только разные типы данных, от того и разная скорость... однако, глядя на экран с ответами, можно увидеть "треугольнички единиц", которые дополняют почти все варианты B) Можно, использовать эту "фишку", для этого в начале проинициализировать используемый массив (prefix) одними единицами:

int main(int argc, char* argv[]){

unsigned number = 0;

cout << "Input number:"; cin >> number;

unsigned *prefix = new unsigned[ number ];

for( unsigned i=0;i<number;i++ )prefix[ i ] = 1; // маленькая фишка

Analyze( number, number-1, prefix, 0 );

delete []prefix;

cout << endl << "Press any key...", getch();

return 0;

}

теперь можно в блоке "// Итерации" функции Analyze использовать предзаполненные ячейки массива

// Итерации

for( unsigned i=rest < step ? rest : step;i;--i ){

prefix[ prefix_size ] = i;

if( i == 1 ){

// сразу переходим к концу цикла с единицами!!

Analyze( 0, i, prefix, prefix_size + (rest - i) + 1 );

} else{

Analyze( rest - i, i, prefix, prefix_size + 1 );

}

---
Результаты без вывода на консоль для числа 75 мин:сек.доли_сек

trainer - 0:7.83

tserega - 0:1.12

experimenter - 1:13.8

tserega2 - 0:1.35

flex ferrum - 2:9.35

самый быстрый алгоритм у tserega :) запустил его на числе 120 и сравнил алгоритмом, что я описал выше

tserega - 5:2.49

tserega2 - 6:31.83

sazabis - 1:37.65

При росте числа - выгрыш растет в геометрической ? прогрессии :)

Однако вариант предложенный trainer показал себя с наилучшей стороны и переплюнул все остальные почти в два раза :yes:

Но и его можно было улучшить используя данную "фишку", только конкретно под этот вариант пришлось создать массив "1+1+1+...+1\n\0"; и подставлять в хвосты с соответствующим сдвигом :)

время работы такого алгоритма для числа 75 - 0:1.30, для 120 - 4:54.3 ( набирает обороты при больших числах и обгоняет tserega :) )
с выводом на эран обгоняет вариант trainer с разницей ~ в разницу работы алгоритмов.

Задача №4

redfred — Mon, 05 Apr 2004 18:20:34 +0000

redfred: Прошу мой вариант снять с конкурса. Он был нацарапан для примера, не претендовал на гениальность, и сразу оговаривалось, что не годится для больших чисел. Разумеется, более оптимальными являются решения, перебирающие не все возможные варианты, а только те которые по сумме совпадают :)

Задача №4

tserega — Mon, 05 Apr 2004 15:19:30 +0000

tserega: А если без учета вывода на экран?

Задача №4

Sazabis — Mon, 05 Apr 2004 14:59:06 +0000

Sazabis: потестил на числе 40 хватило. Время в сек.доли_сек

краткий обзор решений

redfred - недождался, нахождение решения медленние чем вывод на экран.

trainer - 10.76

tserega - 20.15

experimenter - 20.53

// спец. для tserega, другой вар, был прислан в приват

tserega2 - 19.28

flex ferrum - 19.64

Самым хитрым оказался trainer, он сразу формировал строку, а потом выводил на экран. В остальных случаях почти все время съедал вывод на экран. В варианте flex ferruma похоже все ушло на std::string, хотя для решения вполне достаточно 1 массива, вмещающего максимальный ряд.

...
еще добавлю коментарии завтра, сегодня уже мне пора.

Задача №4

Flex Ferrum — Mon, 05 Apr 2004 07:02:45 +0000

Flex Ferrum: Ну, как еще один вариант:

void DoSplit(int num, const std::string& str, int max)

{

char buff[16];

for (int n = min(max, num); n > 0; n --)

{

std::string tmp_str(str);

if (!tmp_str.empty())

tmp_str +="+";

tmp_str += _itoa(n, buff, 10);

if (n == num && !str.empty())

std::cout << tmp_str << std::endl;

else

DoSplit(num - n, tmp_str, n);

}

void SplitInt(int num)

{

DoSplit(num, "", num);

}

но эффективным его не назовешь...

Задача №4

Sazabis — Mon, 05 Apr 2004 06:03:57 +0000

Sazabis: Похоже вариантов больше не будет, сегодня подведу итоги и отпостю.

Задача №4

experimenter — Sun, 04 Apr 2004 07:44:35 +0000

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

#include <iostream>

#include <vector>

#define MIN(a,b) a < b ? a : b

using namespace std;

void ProduceSum(vector <unsigned int> &n, unsigned int max);

int main(int argc, char* argv[])

{

unsigned int num;

vector <unsigned int> v;

while(cin>>num)

{

ProduceSum(v,num);

}

return (0);

}

void ProduceSum(vector <unsigned int> &n, unsigned int reminder)

{

int i;

if(!reminder)

{

if(n.size() == 1) return;

for(i = 0; i < n.size() - 1; i++)

cout<<n[i]<<"+";

cout<<n[i]<<endl;

}

else

{

unsigned int

newMax = (n.empty()) ? reminder : MIN(*(n.end() - 1), reminder);

for(i = 1; i <= newMax; i++)

{

n.push_back(i);

ProduceSum(n, reminder - i);

n.erase(n.end() - 1);

}

return;

}

Задача №4

trainer — Sun, 04 Apr 2004 06:15:33 +0000

trainer: Я так понимаю, вариантов больше не будет. :)
Sazabis, в качестве итога чего-нибудь скажешь?

Задача №4

tserega — Wed, 31 Mar 2004 14:22:35 +0000

tserega: Мое решение (правда, выдает в обратном порядке):

#include <iostream.h>

#define maxSize 10000

void main() {

long m[maxSize];

long l = 0;

long N = 5;

//Main code

m[0] = N;

while (1 == 1) {

int k = l;

while (k >= 0) {

if (m[k] > 1) {

break;

}

k--;

}

if (k < 0) {

break;

}

m[k]--;

long s = 1 + l - k;

l = k;

while (s > 0) {

k++;

if (s < m[k - 1]) {

m[k] = s;

s = 0;

} else {

m[k] = m[k - 1];

s -= m[k];

}

l++;

}

for (int i = 0; i < l; i++) {

cout << m[i] << "+";

}

cout << m[l] << endl;

}

Задача №4

Sazabis — Wed, 31 Mar 2004 14:18:58 +0000

Sazabis:

Цитата

tserega, 31.03.04, 16:43
Sazabis, какое ограничение по N?

в общем нет, я просто посмотрю на цифре, на которой будет видна на глаз разница между разными алгоритмами

я думаю больше 1000 не понадобится

Цитата

tserega, 31.03.04, 16:43
Ограничение по времени есть?

тоже нет, просто сравню чей быстрее.
Этот алгорим работает дольше чем больше цифра, потому все просто - если на 100 не будет видно разницы - запущу на 200

Я олимпиадные задачки не вел, так что извиняюсь - все кустарным способом.
зы Хотя было бы проще если все было в in.txt - out.txt и время работы проги...

Задача №4

tserega — Wed, 31 Mar 2004 13:43:26 +0000

tserega: Sazabis, какое ограничение по N? Ограничение по времени есть?

Задача №4

KAV — Wed, 31 Mar 2004 13:35:05 +0000

KAV: Будут, как только появится свободное время. Завтра на уроках, например :D

Задача №4

Flex Ferrum — Wed, 31 Mar 2004 11:53:28 +0000

Flex Ferrum:

Цитата

Sazabis, 31.03.04, 14:24
2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )

Будут :)

Задача №4

Sazabis — Wed, 31 Mar 2004 11:24:46 +0000

Sazabis: 2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )

Задача №4

trainer — Wed, 31 Mar 2004 04:13:19 +0000

trainer: Вот мой вариант.
Только не спрашивайте о том, как он работает. :D

Задача №4

redfred — Tue, 30 Mar 2004 13:04:54 +0000

redfred: Верно. Каюсь. Небрежно закодировал :)

Исправленный вариант:

static int nN; // Заданное число.

static int * pN; // Накопитель слагаемых.

static int iN; // Счетчик накопителя.

void GoProcedure( int x ); // Рекурсивная процедура.

void ShowSumElems( int N )

{

nN = N;

pN = new int[N+1];

iN = 0;

for( int x=1; x<N; x++ ) GoProcedure(x);

delete pN;

}//---------------------------------------------------------------------------

int Sum() { int s=0; for( int i=0; i<iN; i++ ) s += pN[i]; return s; }

//---------------------------------------------------------------------------

void GoProcedure( int x )

{

if(iN == nN) return; // Условия выхода из рекурсии.

pN[iN++] = x;

if( nN == Sum() )

{

for( int i=0; i<iN; i++ ) // Печатаем подходящий вариант.

{

if( i ) printf("+");

printf("%i",pN[i]);

} printf("\n");

goto SKIP_RECURSION; // На зло противникам оператора goto :)

}

for( int ix=x; ix < nN; ix++ ) GoProcedure( ix ); // Выходим на следующую ступень рекурсии.

SKIP_RECURSION: iN--;

}//---------------------------------------------------------------------------

Задача №4

Sazabis — Tue, 30 Mar 2004 12:46:52 +0000

Sazabis: redfred,
для 6:
1+1+1+1+1+1
1+1+1+1+2
1+1+1+3
1+1+2+2
1+1+4
1+2+3
1+5

например нет 3 + 3. 4 + 2 и т.д

Задача №4

redfred — Tue, 30 Mar 2004 12:17:39 +0000

redfred: Красивая задачка !

Для чисел N допускающих простой перебор вариантов сгодится такой рекурсивный вариант.

static int nN; // Заданное число.

static int * pN; // Накопитель слагаемых.

static int iN; // Счетчик накопителя.

void GoProcedure( int x ); // Рекурсивная процедура.

void ShowSumElems( int N ) // РЕШЕНИЕ ЗАДАЧИ.

{

nN = N;

pN = new int[N+1];

iN = 0;

GoProcedure(1);

delete pN;

}//---------------------------------------------------------------------------

int Sum() { int s=0; for( int i=0; i<iN; i++ ) s += pN[i]; return s; }

//---------------------------------------------------------------------------

void GoProcedure( int x )

{

if(iN == nN) return; // Условия выхода из рекурсии.

pN[iN++] = x;

if( nN == Sum() )

{

for( int i=0; i<iN; i++ ) // Печатаем подходящий вариант.

{

if( i ) printf("+");

printf("%i",pN[i]);

} printf("\n");

goto SKIP_RECURSION; // На зло противникам оператора goto :)

}

for( int ix=x; ix < nN; ix++ ) GoProcedure( ix ); // Выходим на следующую ступень рекурсии.

SKIP_RECURSION: iN--;

}//---------------------------------------------------------------------------

Вариант перебирает N^N/2 вариантов. Думаю, на числе N=20 комп загнется. Для больших чисел нужны более изящные варианты :))

Задача №4

Sazabis — Tue, 30 Mar 2004 11:08:38 +0000

Sazabis:

Цитата

trainer, 30.03.04, 13:55
Комбинации, образованные перестановкой слагаемых - это один вариант или разные?
Например, 1+2 и 2+1

либо 1+2, либо 2+1

аналогично для 4
либо 2+1+1, либо 1+2+1, либо 1+1+2
в ответе может быть только 1 вариант

порядок не важен! но так как проверятся это будет глазами :) желательно упорядоченно!

Цитата

Lepricon, 30.03.04, 14:00
N - натуральное или всё-таки целое?

пусть N будет unsigned int ( все-таки программеры по своему цифры различают, нежели математики :) )

Задача №4

Lepricon — Tue, 30 Mar 2004 11:00:22 +0000

Lepricon: N - натуральное или всё-таки целое?

Задача №4

trainer — Tue, 30 Mar 2004 10:55:32 +0000

trainer: Комбинации, образованные перестановкой слагаемых - это один вариант или разные?
Например, 1+2 и 2+1
Слагаемые в произвольном порядке или в порядке неубывания или возрастания?

Задача №4

Sazabis — Tue, 30 Mar 2004 10:37:34 +0000

Sazabis: Задача
Дано число от 1 до N, где N натуральное число.
Вывести на экран все возможные комбинации чисел ( от 1 до N-1 ) в сумме дающих заданное число. Формат вывода: <число>+<число>+ ... +<число><символ конца строки>

Пример для числа 3
1+1+1
2+1

Пример для числа 5
1+1+1+1+1
2+1+1+1
2+2+1
3+2
3+1+1
4+1