Перейти к содержимому

Фото
- - - - -

Алгоритм


  • Вы не можете создать новую тему
  • Please log in to reply
10 ответов в этой теме

#1 OzzY

OzzY

    Великий и Ужасный

  • Пользователь
  • 461 сообщений

Отправлено 21 марта 2006 - 18:19

Привет.
Как бы вы реализовали такую задачу(ваш алгоритм)?:

Задано некоторое число(например 15), дано определенное количество других чисел, например,
2-две штуки,
3-5 штук,
1-10 штук,
7-одна штука.
...и т.д.
Число задает пользователь количество цифр и какие цифры, тоже задает пользователь. Нужно найти все возможные варианты составить это число из имеющихся. В данном случае(чтобы составить 15):
возьмем
10 и 1 -пять штук; или
10, 3, 2; или
7, 3- две штуки, 2;

и т.д.

Есть мысли? :blink:
  • 0

#2 Cryptoboy

Cryptoboy
  • Пользователь
  • 280 сообщений

Отправлено 22 марта 2006 - 12:14

ну очевидно такое решение


	#include <iostream>
	
	using namespace std;
	
	#define _MAX 100
	
	int c[_MAX + 1];
	int u[_MAX + 1];
	
	int a;
	
	void rec(int n, int k)
	{
		 if (n == 0)
		 {
			   cout << a << " = ";
			   bool first = true;
			   for (int i = 1; i <= _MAX; i++)
				 for (int j = 1; j <= u[i]; j++)
				 {
				   if (first) cout << i;
				   else cout << "+" << i;  
				   first = false;
				 }
			  cout << endl;
		 }
		 else
		 {
			 for (int i = k; i <= _MAX; i++)
			 {
				 if ((c[i] > 0) && (n - i >= 0))
				 {
						  c[i]--; 
						  u[i]++;
						  rec(n - i, i);
						  u[i]--;
						  c[i]++;
				 }				 
			 }
		 }
	}
	
	int main()
	{		 
		memset(c, 0, sizeof(c));
		memset(u, 0, sizeof(u));
		c[2] = 2;
		c[3] = 5;
		c[1] = 10;
		c[7] = 1; 
		a = 15;	 
		rec(a, 1);   
	}

Интереснее когда надо проверить возможность разложения или найти только одно разложение ,, тогда решается не перебором..
  • 0

#3 OzzY

OzzY

    Великий и Ужасный

  • Пользователь
  • 461 сообщений

Отправлено 22 марта 2006 - 19:39

хм...не понятно так. Спасибо, конечно, за код, но мне хотелось бы услышать именно алгоритм...что вы проверяете, что за циклы и т.д. ...
  • 0

#4 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 10 668 сообщений
  • Откуда:Таллин

Отправлено 23 марта 2006 - 19:32

Братцы, а разве эта задача не решается чисто математически?
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#5 OzzY

OzzY

    Великий и Ужасный

  • Пользователь
  • 461 сообщений

Отправлено 23 марта 2006 - 20:23

ну так выложи свой вариант, мне не нужен код...как бы ты стал ее решать? Поделись, интерестно...
  • 0

#6 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 10 668 сообщений
  • Откуда:Таллин

Отправлено 24 марта 2006 - 01:57

OzzY, хе. Это надо вспомнить формулы перестановок, найти листочек бумаги и ручку. Если решу, выложу. А сегодня я умаялся уж.
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#7 OzzY

OzzY

    Великий и Ужасный

  • Пользователь
  • 461 сообщений

Отправлено 27 марта 2006 - 09:12

ап

неужели ни у кого нет свежих мыслей? активней, товарисчи, активней!
  • 0

#8 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 10 668 сообщений
  • Откуда:Таллин

Отправлено 27 марта 2006 - 11:27

OzzY, извини. У меня усилок погорел, я уже неделю кроме паяльника ничего не вижу :(
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#9 V^v

V^v
  • Пользователь
  • 316 сообщений

Отправлено 27 марта 2006 - 12:50

чем не устраивает приведенный код? или непонятно?
  • 0
int main(void)

#10 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 10 668 сообщений
  • Откуда:Таллин

Отправлено 27 марта 2006 - 15:44

V^v, я код не смотрел, но автор говорит что решается перебором. Здесь, мое скромное имхо можно без перебора обойтись...
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#11 OzzY

OzzY

    Великий и Ужасный

  • Пользователь
  • 461 сообщений

Отправлено 27 марта 2006 - 18:06

Да, я С++ не очень...если только С. Да и лучше алгоритмом расскажите, код хоу сам пробовать...
  • 0