Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
242
0 / 0 / 0
Регистрация: 30.12.2010
Сообщений: 3
#1

О велосипедном замке - C++

30.12.2010, 19:28. Просмотров 846. Ответов 1
Метки нет (Все метки)

Никто случайно не имеет текста программы. Задача о велосипедном замке на Си.
Если у кого есть помогите а? Может кто то сталкивался с такой

Суть программы:
комбинационный замок для велосипеда, состоящий из набора N переключателей, каждый из которых может быть в положении «вкл» или «выкл». Замок открывается только при одном наборе положений переключателей, из которых не менее \ N/2J (целая часть от N/2) находятся в положении «вкл». Пред1ю-ложим, что мы забыли эту комбинацию, а нам надо отпереть замок. Предположим также, что мы готовы перепробовать (если необходимо) все комбинации. Нам нужен алгоритм для систематического генерирования этих комбинаций. Если проигнорировать условие \ N/2J, то для замка существует 2 возможных комбинаций. (Покажите, что это так.) Неплохие шансы иайти правильную комбинацию могут быть при N10. Однако условие \ N/2J позволит отбросить (или лучше не генерировать) многие комбинации.

Промоделируем каждую возможную комбинацию вектором из нулей и единиц. На i-м месте будет 1, если г-й переключатель находится в положении «вкл», и О, если i-й переключатель -• в положении «выкл». Множество всех возможных Л-векторов хорошо моделируется с помощью двоичного дерева. Каждая вершина k-ro Уровня этого дерева будет соответствовать определенному набору первых k компонент yV-вектора. Две ветви, идущие вниз из вершины этого уровня, соответствуют двум возможным значениям (&+1)-й компоненты в /V-векторе. У дерева будет уровней. Рис. 3.3.1 на примере N=4 поясняет основную конструкцшс).

Условие, заключающееся в том, что число переключателей в положении «вкл» должно быть не меньше [. N/2 J , позволяет нам не образовывать части дерева, которые не могут привести к правильной комбинации. Например, рассмотрим вершину 00 на рис. 3.3.1. Так как правая ветвь (к ООО) не может привести к допустимой комбинации, нет нужды ее формировать. Если какие-то вершины, следующие за рассматриваемой вершиной, не удовлетворяют ограничению задачи, то эти вершины не надо рассматривать. В данном случае никакие из вершин, находящихся внутри пунктирных линий, не нужно исследовать и даже формировать.
Миниатюры
О велосипедном замке  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.12.2010, 19:28     О велосипедном замке
Посмотрите здесь:

Save для Silent Hill 2 рядом с коробкой на замке
C# "О велосипедном замке" на C#

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
31.12.2010, 00:22     О велосипедном замке #2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <malloc.h> 
 
void rec(int *a, int col_0, int n, int i)
{
    if(col_0>n/2)
        return;
    if(i==n)
    {
        for(int j=0; j<n; j++)
            printf("%d", a[j]);
        printf("\n");
        return;
    }
    a[i]=0;
    rec(a, col_0+1, n, i+1);
    a[i]=1;
    rec(a, col_0, n, i+1);
}
 
int main()
{
        int n, *a;
        printf("N= ");
        scanf("%d", &n);
        a=(int*) malloc(n*sizeof(int));
        rec(a, 0, n, 0);
        return 0;
}
Yandex
Объявления
31.12.2010, 00:22     О велосипедном замке
Ответ Создать тему
Опции темы

Текущее время: 09:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru