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

Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.98
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
05.10.2010, 21:11     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #1
Какое минимальное количество спичек нужно для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку?

Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку?
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2010, 21:11     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку
Посмотрите здесь:

C++ Указать номер того человека, для обслуживания которого потребовалось минимальное время
что нужно заметить для того чтобы получился прямоугольник ? C++
Найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние C++
Какое минимальное число букв необходимо заменить в слове Х, с тем, чтобы оно стало перевертышем? C++
C++ когда вводится нуль,то программа не работает,нужно добавитть еще какое-то условие для нуля ,но я не знаю какое
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
05.10.2010, 21:12  [ТС]     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #2
на рисунку: для построения 3 кубов нужно 28 спичек
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
05.10.2010, 21:22     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #3
Mayonez, если N квадратов то спичек нужно 4*N
если N кубов то 12*N
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
05.10.2010, 22:00  [ТС]     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #4
для 3 кубов нужно 28 спичек (на рисунку), в не 12*N=12*3=36
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
06.10.2010, 13:43     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #5
тут какая то формула нужна...не могу найти

Добавлено через 11 минут
C++
1
2
3
4
5
6
7
8
    int n,m;
     m=n=0;
     cin>>m;
     while(m>=1){
     n=n+8;
         m--;
     }
 cout<<n+4<<endl;
Добавлено через 58 секунд
Mayonez, не знаю правильно или нет,но когда ввожу 3 выводит 28
mamedovvms
2913 / 834 / 93
Регистрация: 30.04.2009
Сообщений: 2,613
06.10.2010, 14:44     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #6
Conter = целая часть(sqrt(n)) - число кубов(квадратов) в одной строке или одном столбце
unit = целая часть(sqrt(n)) -1; - Общих Спичек в одной строке или одном столбце
ostatok = n - sqr(Counter);

rezult = n*12 - unit*Conter*4*2 - 4*2*ostatok+1 для кубов
rezult = n*4 - unit*Conter*2 - 2*ostatok+1 для квадратов

если я не ошибся в расчетах то должно работать для n > 3

Добавлено через 2 минуты
Хотя можно чуть чуть изменить и будет работать и для чисел от 1 до 3 тоже, я думаю вы понял что квадраты можно выкладывать не только встроку, но и как матрица

Добавлено через 1 минуту
хотя еще есть один вариант решения этой задачи
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
06.10.2010, 15:51     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #7
Цитата Сообщение от mamedovvms Посмотреть сообщение
хотя еще есть один вариант решения этой задачи
какой
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
06.10.2010, 16:25     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #8
формула для расчета минимального количества спичек для квадратов
S=10+(N-3)*3-N%3
Где N количество квадратов
N%3 Целочисельное деление на 3

Просчитал до N=10
Дальше лень) но нужно проверить
mamedovvms
2913 / 834 / 93
Регистрация: 30.04.2009
Сообщений: 2,613
07.10.2010, 07:31     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #9
Цитата Сообщение от ^Tecktonik_KiLLeR Посмотреть сообщение
какой
вот такой
n - количество квадратов
p = sqrt(n);
t = n - sqr(p);
k = 1 если t <> 0 иначе k = 0
rezult = n*4 - 2*(p-1) - 2*sqr(p-1) - k*(1) - k*(2*(t - 1));
точно работает для n>3

Добавлено через 5 минут
Цитата Сообщение от LineStown Посмотреть сообщение
S=10+(N-3)*3-N%3
по моему на работает для 3
может быть я что то не правильно считаю, большая просьба напишите для 2 и для 3
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
07.10.2010, 10:48     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #10
Во расчитал

Добавлено через 33 секунды
при N <=3 S=10+(N-3)*3
при N > 3 S=10+(N-3)*3-N%3
Svett
0 / 0 / 0
Регистрация: 09.04.2010
Сообщений: 3
07.10.2010, 11:32     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #11
Проверь вот такую формулу, вроде подходит: 4*(N+1)+4*N
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
07.10.2010, 16:07     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #12
Очевидно, что наиболее компактная фигура из квадратов получится, если мы будем присоединять к ней квадраты последовательно по спирали.
Т.е. строим максимально возможный квадрат со стороной s, на что уходит k = 2*s*(s+1) спичек, затем к нему пристраивается ряд длиной s, и еще один длиной (s + 1), пока не дойдем до нужного количества квадратов. На первый квадрат каждого ряда тратится три спички, а на остальные квадраты - две.
Т.е. общее количество спичек равно k, плюс 3, умноженное на номер p дополнительного ряда, в котором мы находимся (1 или 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
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cmath>
////////////////////////////////////////////////////////////////////////////////////////
int matches_quantity_for_squares(int  n)
{
    int s = static_cast<int>(floor(sqrt(static_cast<double>(n))));
    int k = n - s * s;
    int p = (k == 0) ? 0 : (k - 1)/s + 1;
    return 2*s*(s+1) + p*3 + (k-p)*2;
}
////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int  squares_count;
        do
        {
            std::cout << "число квадратов > 0 = ";            
            std::cin >> squares_count;        
        }while(squares_count <= 0);
 
        std::cout <<     "количество спичек   = "
                  << matches_quantity_for_squares(squares_count)
                  << std::endl
                  << std::endl
                  << std::endl;    
    }
}
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
07.10.2010, 17:24     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #13
Последняя формула верная) У меня идет перерасход по 1-й спичке каждый ряд.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2010, 20:43     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку
Еще ссылки по теме:

C++ Дана строка. Определить минимальное количество символов, которые нужно добавить, чтобы получить палиндром
Найти количество операций необходимое для того, чтобы получить из второй строки первую C++
Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной C++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
07.10.2010, 20:43     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку #14
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/////////////////////////////////////////////////////////////////////////////////////////
//  Какое минимальное количество спичек нужно для того, чтобы построить 
//  в пространстве N кубов со стороной в одну спичку? 
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cmath>
////////////////////////////////////////////////////////////////////////////////////////
int matches_quantity_for_gran(int  n)
{
    /*
    Используем функцию для подсчета минимального количества спичек из предыдущей
    задачи, с подсчетом еще и вертикальных спичек.
 
    int matches_quantity_for_squares(int  n)
    {
        int s = static_cast<int>(floor(sqrt(static_cast<double>(n))));
        int k = n - s * s;
        int p = (k == 0) ? 0 : (k - 1)/s + 1;
        return 2*s*(s+1) + p*3 + (k-p)*2;
    }
 
    Тогда для квадрата со стороной s вместо количества спичек 2*s*(s+1) 
    будет 2*s*(s+1) + (s + 1)*(s + 1),
    p будет умножаться не на 3, а на 5, 
    а (k-p) не на 2, а на 3.
    */
    if(n == 0)
    {
        return 0;
    }
    int s = static_cast<int>(floor(sqrt(static_cast<double>(n))));
    int k = n - s * s;
    int p = (k == 0) ? 0 : (k - 1)/s + 1;
    //return 2*s*(s+1) + p*3 + (k-p)*2;
    return 2*s*(s+1) + (s + 1)*(s + 1) + p*5 + (k-p)*3;
}
////////////////////////////////////////////////////////////////////////////////////////
int matches_quantity_for_cubes(int  n)
{    
    //Очевидно, что наиболее компактная фигура из кубов получится, если мы будем 
    //строить фигуру следующим образом. 
    //Строим максимально возможный куб со стороной s, на который затрачивается
    //3*(s+1)^2*s спичек.
    int s = static_cast<int>(floor(pow(static_cast<double>(n), 1.0/3.0)));
    int res = 3 * (s + 1) * (s + 1) * s;
    int k = n - s*s*s;
    if(k == 0)
    {
        return res;
    }
 
    //К этому кубу нам надо достраивать три грани размерами:
    //1) s x s, 
    //2) s x (s + 1)
    //3) (s + 1) x (s + 1),
    //пока не получим нужное количество кубов.
        
    int gran_1_cubes_count = s * s;
    int gran_2_cubes_count = s * (s + 1);
 
    if(k >= gran_1_cubes_count)    
    {
        res += matches_quantity_for_gran(gran_1_cubes_count);
        k -= gran_1_cubes_count;
        if(k >= gran_2_cubes_count)
        
        {
            res += matches_quantity_for_gran(gran_2_cubes_count);
            k -= gran_2_cubes_count;                    
        }
    }
    return res + matches_quantity_for_gran(k);  
}
////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int  cubes_count;
        do
        {
            std::cout << "число кубов > 0   = ";            
            std::cin >> cubes_count;        
        }while(cubes_count <= 0);
 
        std::cout <<     "количество спичек = "
                  << matches_quantity_for_cubes(cubes_count)
                  << std::endl
                  << std::endl
                  << std::endl;    
    }
}
Yandex
Объявления
07.10.2010, 20:43     Какое минимальное количество спичек нужно для того, чтобы построить в пространстве N кубов со стороной в одну спичку
Ответ Создать тему
Опции темы

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