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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.98
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

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

05.10.2010, 21:11. Просмотров 5408. Ответов 13
Метки нет (Все метки)

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

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

Какое минимальное число монет нужно перевернуть, чтобы все монеты лежали одинаковой стороной вверх? - C++
Всем привет прошу помощи или же направления в решение задачи! 1) На столе лежат n монеток. Некоторые из них лежат вверх решкой, а...

Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной - C++
Добрый вечер, наткнулся на простую задачу - сложность всего лишь 8%. Её нужно решить с использованием цикла for. Задачу, я, конечно, решил,...

Рассчитать какое минимальное количество топлива необходимо для дозаправки самолету - C++
Используйте пожалуйста только if и switch :) если это реально.. Задание 1: Грузовой самолет должен пролететь с грузом из пункта А в пункт...

Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков? - Free Pascal
Спичечная модель Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина...

Какое минимальное время понадобится кораблю для того, чтобы достичь точки? - Delphi
Заранее спасибо!

Какое минимальное количество точек на кривой еще нужно определить, чтобы идентифицировать такого типа кривую? - Геометрия
Помогите пожалуйста с этим (картинка в приложении): 1) Если координаты точек кривой Z1 и Z2 уже известны, то какое минимальное...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
05.10.2010, 21:12  [ТС] #2
на рисунку: для построения 3 кубов нужно 28 спичек
0
^Tecktonik_KiLLeR
1160 / 442 / 22
Регистрация: 23.06.2009
Сообщений: 6,245
Завершенные тесты: 1
05.10.2010, 21:22 #3
Mayonez, если N квадратов то спичек нужно 4*N
если N кубов то 12*N
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
05.10.2010, 22:00  [ТС] #4
для 3 кубов нужно 28 спичек (на рисунку), в не 12*N=12*3=36
0
^Tecktonik_KiLLeR
1160 / 442 / 22
Регистрация: 23.06.2009
Сообщений: 6,245
Завершенные тесты: 1
06.10.2010, 13:43 #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
0
mamedovvms
2917 / 838 / 93
Регистрация: 30.04.2009
Сообщений: 2,627
06.10.2010, 14:44 #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 минуту
хотя еще есть один вариант решения этой задачи
0
^Tecktonik_KiLLeR
1160 / 442 / 22
Регистрация: 23.06.2009
Сообщений: 6,245
Завершенные тесты: 1
06.10.2010, 15:51 #7
Цитата Сообщение от mamedovvms Посмотреть сообщение
хотя еще есть один вариант решения этой задачи
какой
0
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
06.10.2010, 16:25 #8
формула для расчета минимального количества спичек для квадратов
S=10+(N-3)*3-N%3
Где N количество квадратов
N%3 Целочисельное деление на 3

Просчитал до N=10
Дальше лень) но нужно проверить
0
mamedovvms
2917 / 838 / 93
Регистрация: 30.04.2009
Сообщений: 2,627
07.10.2010, 07:31 #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
0
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
07.10.2010, 10:48 #10
Во расчитал

Добавлено через 33 секунды
при N <=3 S=10+(N-3)*3
при N > 3 S=10+(N-3)*3-N%3
0
Svett
0 / 0 / 0
Регистрация: 09.04.2010
Сообщений: 3
07.10.2010, 11:32 #11
Проверь вот такую формулу, вроде подходит: 4*(N+1)+4*N
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.10.2010, 16:07 #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;    
    }
}
1
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
07.10.2010, 17:24 #13
Последняя формула верная) У меня идет перерасход по 1-й спичке каждый ряд.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.10.2010, 20:43 #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;    
    }
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2010, 20:43
Привет! Вот еще темы с ответами:

Какое минимальное количество действий нужно выполнить над первым словом, чтобы оно совпадало со вторым? - Pascal ABC
Дано два слова. Какое минимальное количество действий нужно выполнить над первым словом,чтобы оно совпадало со вторым

Найти минимальное количество поездок машиниста для того, чтобы сформировать три состава - Visual Basic
Текст задачи: Железнодорожное полотно разветвляется на два тупика В и С. К этому разъезду подходит состав (не более 255 вагонов)....

Определить минимальное количество операций необходимо для того, чтобы сделать число a равным числу b - Turbo Pascal
Помогите пож-ста срочно

Посчитайте, какое минимальное количество камней нужно убрать со стола - Free Pascal
Помогите пожалуйста решить: На столе в ряд выложены n камней, каждый из которых может быть красного, зеленого или синего цвета....


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.10.2010, 20:43
Ответ Создать тему
Опции темы

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