Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
2 / 2 / 4
Регистрация: 03.06.2011
Сообщений: 23
1

Не могу понять алгоритм. Как именно он работает

07.07.2011, 15:19. Просмотров 857. Ответов 7
Метки нет (Все метки)

Не могу понять сам алгоритм. Как именно он считает.

Само задание: дано n блоков, какое количество всевозможных лестниц можно из них построить?
Если, рассматривая лестницу вертикально, принять, что ее уровни будем обозначать (снизу вверх): k1, k2, k3, ... ,km. То обязательно выполнение условия: k1>k2>k3>...>km. Словесно: каждый последующий слой меньше предыдущего, хотя бы на единицу.

Есть код на С++:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <time.h>
#include <cmath>
using namespace std;
 
///algo lesenka
 
int pr(int x)
{
        int k=1;
        int s=0;
        while (k<x)
        {
                k=k*2;
                s++;
        }       
        return s;       
}
 
int a[10000];
int main()
{               
        int n;  
        
        freopen("input.txt","rt",stdin); 
        freopen("output.txt","wt",stdout);
        cin >>n;        
        clock_t start = clock();  //timer start 
        int k=pr(n);
        int i;
        int count=0;
        while (true)
        {
                i=0;
                a[i]=a[i]+1;
                while (a[i]>n)
                {
                        a[i]=0;
                        i=i+1;
                        a[i]=a[i]+1;
                }               
                if (i>k) break;
                int s=0;int q=0;int f=0;
                for (int j=k;j>=0;j--)
                {
                        if (f==0 && a[j]==0) continue;else f=1;
                        s=s+a[j];
                        if (a[j]<=a[j+1]) q=1;
                        
                }               
                if (s==n && q==0)  count++;                     
                
        }
        clock_t finish = clock();   //timer end;
    double duration = (float)(finish - start) / CLOCKS_PER_SEC; //время окончания выполнения программы  в сек. (start-end)
        cout <<"Время выполнения метода :"<<duration<<" sek"<<endl;
        cout <<"ans: "<<count<<endl;
        return 0;
}
Есть он же, переписаный под FPC:
Pascal
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
program Project1;
 
uses windows;
 
var
 duration:cardinal;
 InputFile, OutputFile : text;
 n, k, count, index, s, q, f, j : integer;
 flag : Boolean;
 a : array [ 1..1000 ] of integer;
 
function Pr ( x : Integer ) : integer;
var
 k, s : integer;
begin
 k := 1; s := 0;
 while ( k < x ) do
 begin
 k := k * 2;
 s := s + 1;
 end;
 Pr := s;
end;
 
begin
 write('введи n= ');
 readln(n);
 duration:=GetTickCount();
 k := Pr ( n ) + 1;
 count := 0;
 for index := 1 to k + 1 do
 a [ index ] := 0;
 flag := true;
 while ( flag ) do
 begin
 index := 1;
 a [ index ] := a [ index ] + 1;
 while ( a [ index ] > n ) do
 begin
 a [ index ] := 0;
 index := index + 1;
 a [ index ] := a [ index ] + 1;
 end;
 if ( index > k ) then
 flag := false
 else
 begin
 s := 0;
 q := 0;
 f := 0;
 for j := k + 1 downto 1 do
 begin
 if ( ( f = 0 ) and ( a [ j ] = 0 ) ) then
 Continue
 else
 f := 1;
 s := s + a [ j ];
 if ( a [ j ] <= a [ j + 1 ] ) then
 q := 1;
 end;
 
 if ( ( s = n ) and ( q = 0 ) ) then
 count := count + 1;
 end;
 end;
 duration:=GetTickCount()-duration;
 writeln('Лесенок: ', count);
 writeln('Время выполнения: ',duration,' мсек');
 readln;
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.07.2011, 15:19
Ответы с готовыми решениями:

Не работает код именно при этих значениях переменных, если значения меньше, то работает.Не могу понять причину
Не работает код именно при этих значениях переменных, если значения меньше, то работает.Не могу...

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

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

Символьные литералы, указатели и функция. Не могу понять, почему именно так
Доброго времени суток всем! :) Изучаю С++, всегда стараюсь добить до последнего код, чтобы не...

7
заставил Бендера
854 / 319 / 17
Регистрация: 05.12.2010
Сообщений: 1,706
Записей в блоге: 6
Завершенные тесты: 1
08.07.2011, 13:03 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <time.h>
#include <cmath>
using namespace std;
 
///algo lesenka
 // возвращает сколько шагов сделано.
int pr(int x)
{
        int k=1;
        int s=0;
        while (k<x)
        {
                k=k*2;
                s++;
        }       
        return s;       
}
 
int a[10000];
int main()
{               
        int n;  
        //формируем новый файл из старого
        freopen("input.txt","rt",stdin); 
        freopen("output.txt","wt",stdout);
        //        
cin >>n;    // шаг лесенки
        clock_t start = clock();  //timer start 
        int k=pr(n);
        int i;
        int count=0;
       ///шагаем по лесенке по условию задачи
 while (true)
        {
                i=0;
                a[i]=a[i]+1;
                while (a[i]>n)
                {
                        a[i]=0;
                        i=i+1;
                        a[i]=a[i]+1;
                }               
                if (i>k) break;
                int s=0;int q=0;int f=0;
                for (int j=k;j>=0;j--)
                {
                        if (f==0 && a[j]==0) continue;else f=1;
                        s=s+a[j];
                        if (a[j]<=a[j+1]) q=1;
                        
                }               
                if (s==n && q==0)  count++;                     
                
        }
        clock_t finish = clock();   //timer end;
    double duration = (float)(finish - start) / CLOCKS_PER_SEC; //время окончания выполнения программы  в сек. (start-end)
        cout <<"Время выполнения метода :"<<duration<<" sek"<<endl;
        cout <<"ans: "<<count<<endl;
        return 0;
}
1
2 / 2 / 4
Регистрация: 03.06.2011
Сообщений: 23
08.07.2011, 14:41  [ТС] 3
Я просто не могу понять саму функцию pr. Почему там берется степень двойки?
Как разобрался, в итоге этой функцией сформируется размерность массива, то есть разрядность числа, которое будем перебирать (100, 200, 300, ... ,010, ... ,999). Потом налогаюся условия и, если они выполнены, то count++.
0
3977 / 1704 / 195
Регистрация: 06.10.2010
Сообщений: 3,805
08.07.2011, 16:42 4
Немного не по теме
C
1
2
3
4
5
6
7
8
int k=1;
int s=0;
while (k<x)
{
  k=k*2;
  s++;
}       
return s;
Можно проще
C
1
return 1<<(x-1);
2
2 / 2 / 4
Регистрация: 03.06.2011
Сообщений: 23
08.07.2011, 19:16  [ТС] 5
Цитата Сообщение от murderer Посмотреть сообщение
Немного не по теме
C
1
2
3
4
5
6
7
8
int k=1;
int s=0;
while (k<x)
{
  k=k*2;
  s++;
}       
return s;
Можно проще
C
1
return 1<<(x-1);
Спасибо. но что выполняет данная функция в этом алгоритме? Зачем она вообще нужна?
0
заставил Бендера
854 / 319 / 17
Регистрация: 05.12.2010
Сообщений: 1,706
Записей в блоге: 6
Завершенные тесты: 1
08.07.2011, 20:04 6
Цитата Сообщение от Юр0к Посмотреть сообщение
каждый последующий слой меньше предыдущего, хотя бы на единицу.
вот что.
1
2818 / 1628 / 252
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
08.07.2011, 21:27 7
C++
1
2
3
4
5
6
                while (a[i]>n)
                {
                        a[i]=0;
                        i=i+1;
                        a[i]=a[i]+1;
                }
Гениально, блин.
В этом коде я ничего не понял, но вообще задача про лесенку - это классика динамического программирования.
http://ru.wikipedia.org/wiki/%D0%94%...BD%D0%B8%D0%B5
1
2 / 2 / 4
Регистрация: 03.06.2011
Сообщений: 23
08.07.2011, 21:48  [ТС] 8
Цитата Сообщение от Somebody Посмотреть сообщение
Гениально, блин.
В этом коде я ничего не понял, но вообще задача про лесенку - это классика динамического программирования.
http://ru.wikipedia.org/wiki/%D0%94%...BD%D0%B8%D0%B5
да, классика. решается легко с помощью рекурсии или ДП. Но у меня задание - решить задачу перебором )

Добавлено через 1 минуту
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
вот что.
спасибо
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.07.2011, 21:48

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Не могу понять никак условие, что именно требуется для входных даннных
Народ, есть задачка со следующим условием Из точки А в точку В можно добраться несколькими...

Не могу понять как работает where
Я только начал разбираться в linq, и совершенно не могу понять почему происходит следующие //В...

Не могу понять как работает OR
Начинаю изучать Python. Но не могу понять как работает вот этот скрипт: N = int(input())...

CompareTo. Не могу понять как он работает
Создать класс, в котором определить 2*-3 поля. Переопределить equals, hashcode, compareTo. ...


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

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

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