Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
SMYH
2 / 2 / 1
Регистрация: 23.10.2013
Сообщений: 38
1

Перебов бинарных векторов веса от 1 до w

15.06.2014, 20:10. Просмотров 805. Ответов 5
Метки нет (Все метки)

Нужен алгоритм, который позволит перебрать все вектора длинной n и веса 1 - w.
Например, ввод:
Длина вектора - 4.
Веса - 1 - 3.

Вывод:
Кликните здесь для просмотра всего текста

Веса 1:
0000
0001
0010
0100
1000

Веса 2:
1100
1010
1001
0110
0101
0011

Веса 3:
1110
1101
1011
0111



Для веса 1 - элементарно. Но >1 я не могу ничего придумать. Можно использовать циклический сдвиг, потому что все вектора "вращаются" около нескольких орбит.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2014, 20:10
Ответы с готовыми решениями:

Кластеризация бинарных векторов
Здравствуйте! Я тут недавно и пока что не знаю, как лучше задавать вопросы,но очень нужно...

Какое отклонение веса тела от среднего веса можно гарантировать?
При взвешивании тела получен средний вес m=2,3 г, среднее квадратическое отклонение веса σ=0,02 г....

Почему так(комбинации бинарных и не бинарных вводов и выводов)?
#include <string> #include <iostream> #include <fstream> #include <iomanip> using namespace...

Напечатать в порядке возрастания веса студентов, вес которых не меньше среднего веса всей группы
Известен список фамилий и вес студентов группы(ввод с клавиатуры). Напечатать в порядке...

Создать класс для обработки векторов разность векторов норму векторов
Создать класс для обработки векторов разность векторов норму векторов

5
AdmiralHood
461 / 265 / 88
Регистрация: 15.11.2013
Сообщений: 517
16.06.2014, 06:39 2
А простым перебором недостойно истинного джентльмена? Так, например:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
program Project2;
{$APPTYPE CONSOLE}
const SUM=2;
var i1,i2,i3,i4,i5,i6:integer;
begin
for i1:=0 to 1 do
for i2:=0 to 1 do
for i3:=0 to 1 do
for i4:=0 to 1 do
for i5:=0 to 1 do
for i6:=0 to 1 do
if i1+i2+i3+i4+i5+i6=SUM then writeln(i1,i2,i3,i4,i5,i6);
readln;
end.
000011
000101
000110
001001
001010
001100
010001
010010
010100
011000
100001
100010
100100
101000
110000
1
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
16.06.2014, 12:01 3
Цитата Сообщение от SMYH Посмотреть сообщение
Веса 1:
0000
Что-то не очень на 1 похоже
0
SMYH
2 / 2 / 1
Регистрация: 23.10.2013
Сообщений: 38
16.06.2014, 20:30  [ТС] 4
Достойно. И это рабочий вариант, но это полный перебор. А это увеличение времени работы с ростом параметров.
Но за идею спасибо, как-то сам не догадался проверять вес каждого вектора и выбирать подходящие.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
16.06.2014, 22:47 5
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function go(n) {
  var res=[0], last=(1<<n)-1, x, q, w;
 
  for(q=0; q<n; ++q)
    res.push(1<<q);
 
  for(q=1; res[res.length-1]!=last; ++q)
    for(x=res[q], w=1; !(x&w); w<<=1)
      res.push(x|w);
 
  return res;
}
 
console.log(go(4).map(function(x) {
  return ("000" + x.toString(2)).substr(-4);
}));
1
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
21.06.2014, 09:42 6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Place( const int * A, int total, int start, int rem )
{
 if (start >= total) return;
 Place(A + 1, total, start + 1, rem);
 A[start] = 1;
 if (--rem = 0) 
  PrintA(A, total); 
 else 
  Place(A + 1, total, start + 1, rem);
}
 
const int N = 4;
const int W = 2;
 
int main( void )
{
 int * A = new int[N];
 Place(A, N, 0, W);
 return 0;
}
PrintA допишите сами
0
21.06.2014, 09:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2014, 09:42

Создание бинарных файлов. Чтение и запись бинарных файлов
Здраствуйте. Сколько я не рылся в нете сколько не искал, как то все не доходит до меня тупого). На...

Найти базис системы векторов и координаты всех векторов в найденном базисе
найти базис системы векторов и координаты все векторов в найденном базисе если...

Найти классы аддитивной группы векторов плоскости по подгруппе векторов
Найти классы аддитивной группы векторов плоскости (выходящих из начала координат) по подгруппе...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru