Виконав студент групи K-15
I курсу факультету кібернетики
Бевза Максим
Зміст
1. Умова задачі
2. Постановка задачі
3. Тести
4. Побудова алгоритму
5. Проектування програми
6. Тестування
7. Протокол виправлення помилок
8. Література
9. Додатки
Умова задачі
Написати лабораторну роботу, яка обчислює стани пам’яті та системи керування космічним апаратом на планеті Fort Knox.
Постановка задачі
На планеті Fort Knox зберігаються невичерпні запаси золота. Вони складені в ряд у вигляді злитків прямокутної форми. Кожна цеглинка має розміри xi yi zi і густину ρi.
На цю планету прилетів деякий космічний корабель. Конструкція корабля (окрім двигуна та інших засобів для подорожей) складається з:
1. порожньої ємності об’ємом V м3
2. плавильні (розміри W м (по Oy) на U м (по Oz)), яка використовуючи de енергії за один такт переплавляє шару з dl золота. За такт переплавки маса корабля також зменшується на dm.
3. конвеєра, який може виконувати команди:
· P – покласти наступний злиток на конвеєр.
· С – центрувати.
· R – перевернути вздовж осі Ox.
· T – перевернути вздовж осі Oy.
· A – виконати такт переплавки.
· D – викинути з конвеєра.
На початку компанії по вивозу золота на кораблі є E енергії, його маса M0, мінімальний рівень енергії, потрібний для повернення «додому» E0, максимальна допустима маса M (при масі меншій M двигуни розвинуть достатньої швидкості для виходу на гіперболічну орбіту, при рівній M - на параболічну орбіту, при більшій M – на еліптичну орбіту).
Злитки кладуться на конвеєр координатами xi, yi, zi вздовж відповідно осей Ox, Oy, Oz.
Послідовність псевдовипадкових чисел задається так: Rn = Fibn mod K.
Константи що задаються: V, W, U, K, dl, dm, de, M0, M, E0, E.
Довідкові відомості:
1. Числа Фібоначчі.
Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — числова послідовність Fn, задана рекурентним співвідношенням другого порядку
Числа Фібоначчі щільно пов'язані з золотим перетином 
Формула Біне виражає за допомогою ϕ значення Fn в явному вигляді як функцію від n:
При цьому 
і 
є коренями квадратного рівняння 
.
Оскільки − 1 < 1 − ϕ < 0, знаходимо, що при 
Тому з формули Біне випливає, що для всіх натуральних n, Fn є найближчим до 
цілим числом, 
. Зокрема, справедлива асимптотика 
2. Об’єм і густина.
Об’єм паралелепіпеда розмірами x y z можна знайти за формулою x*y*z.
Масу речовини можна знайти помноживши її густину на об’єм.
3. Послідовність псевдовипадкових чисел.
Можна створити таку послідовність чисел, властивості якої будуть схожі на властивості послідовності випадкових чисел. Такі послідовності називаються псевдовипадковими.
Вперше запропонував їх використовувати Джон фон Нейман у 1946 р. Його метод полягав в наступному: n-розрядне число підносилось до квадрата і з нього вибиралися середні n цифр. Метод був дуже недосконалий, послідовності майже завжди вироджувалися в нуль або зациклювалися з коротким періодом. Пізніше було запропоновано багато різних алгоритмів отримання псевдовипадкових чисел.
В основі програмних генераторів як правило лежать рекурентні формули. Як правило, вони генерують цілі числа рівномірно розподілені на відрізку від 0, до деякого максимального m. Щоб отримати числа з плаваючою комою, рівномірно розподілені на [0,1), кожен отриманий результат ділять на m.
4. Мова програмування C.
C (англ. C) — універсальна, процедурна, імперативна мова програмування загального призначення, розроблена у 1972 роціДенісом Рітчі у Bell Telephone Laboratories з метою написання на ній операційної системи UNIX.
Хоча, С і було розроблено для написання системного програмного забезпечення. наразі вона досить часто використовується для написання прикладного програмного забезпечення.
С імовірно, є найпопулярнішою у світі мовою програмування за кількістю вже написаного на ній програмного забезпечення, доступного під вільними ліцензіями коду та кількості програмістів, котрі її знають. Реалізації компіляторів для мови С існують для багатьох операційних систем та апаратних архітектур. C здійснила великий вплив на інші мови програмування, особливо на C++, яка спочатку проектувалася, як розширення для С, а також на Java та C#, які запозичили у С синтаксис.
Тести
V = 50;
W = 11;
U = 7;
K = 13;
dl = 1;
dm = 8;
de = 40;
M0 = 100;
M = 140;
E0 = 400;
E = 220;
На виході маємо
V = 11
M = 121
E = 240
Побудова алгоритму
Розглянемо всі можливі перестановки чисел x, y, z:
1. xyz
2. x zy
3. y z x
4. y xz
5. z x y
6. z yx
Кожну наступну ми отримуємо з попередньої помінявши місцями виділені змінні (наприклад x zy отримуємо з xyz помінявши місцями 2 останніх елементи).
Переберемо всі перестановки і знайдемо таку, що перша координата буде найбільшою. В цьому випадку ми будемо максимально ефективно використовувати пристрій плавлення (dl = const, тому намагаємось максималізувати площу, яка буде плавитись).
Далі за допомогою команд R і T дійдемо до даної перестановки і поки в нас не перевищені необхідні умови для зльоту будемо плавити золото.
Проектування програми
У нашій програмі буде 3 файли, в кожному файлі будуть наступні функції
F1.c
1.1. fibb
1.2. get_rand
F2.c
2.1. P
2.2. C
2.3. R
2.4. T
2.5. A
2.6. D
F3.c
3.1. swap
3.2. min
3.3. get_x
3.4. main
Функція fibb повертає наступне число Фібоначчі при параметрі 0 і ініціалізує значення початкові значення при параметрі не 0.
Функція get_rand повертає наступне псевдовипадкове число.
Функції P, C, R, T, A, D виконують операції на конвеєрі.
Функція swap міняє місцями два значення xx і yy.
Функція min повертає менше з двох значень.
Функція x повертає значення першого елемента в перестановці з номером параметра.
Функція main виконує всі операції по управлінню космічним апаратом.
Тестування
В ході тестування були виявлені недоліки в програмі. Вони були успішно виправлені і тепер в програмі недоліків не виявлено.
Протокол виправлення помилок
У функції P() стрічка fibb(1); має бути в main(), а не в P().
int P() // Put
{
Fibb(1);
x=get_rand();
y=get_rand();
z=get_rand();
ro=get_rand();
// cur_m = x*y*z*ro;
return 0;
}
При перевірці чи треба плавити до умови x>0 варто додати що добуток усіх змінних x y z ro має бути ненулбовим «while (x*y*z*ro>0»
В функції
int R() // Rotare Ox
{
xx=y;
yy=z;
y==yy;
z==xx;
}
Замість
y==yy;
z==xx;
варто писати
y=yy;
z=xx;
Література
1. www.wikipedia.org
2. Методичні рекомендації до виконання практичних і лабараторних робіт з дисципліни «Програмування» / В. В. Зубенко, Г. А. Кияшко -- К.: «Київський університет», 2005. – 456-470 с.
3. М. Эллис, Б. Строуструп. Справочноеруководство по языку C++ с комментариями: Пер. с англ. - Москва: Мир, 1992. 651с.
Додатки
1. Специфікація мови C.
2. Лістинг програми.
Специфікація мови С
<P>::={<VD>|<FD>}
<VD>::=<IT><WS><IV>{‘,’<IV>}‘;‘
<FD>::=<IT><WS><IF>‘(‘<PD>‘)’’{‘[<SS>]’}’ — Стандарт Ансі
<FD>::=<IT><WS><IF>‘(‘<PL>‘)‘<PS><SS> — Стандарт Кернігана
<PD>::=<IT><WS><IV>[{‘,’<IT><WS><IV>}]
<IT>::=’int’|’char’|’double’|’bool’|’string’|’short’|’unsigned’
<IV>::=<L>|<IV><L>|<IV><NU>
<L>::=’a’|’b’|…|’z’|’A’|’B’|…|’Y’|’Z’|’_’
<NU>::=’0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’
<SS>::=‘{‘{<VD>}{<S>}‘}‘
<S>::=<SS>|‘return’‘(‘<E>‘)‘ ‘;‘|<E>‘;‘
<E>::=<D>{<+-><D>}
<D>::=<M>{<*/%><M>}
<M>::=<A><^><M>
<A>::=<const>|<IV>|’IF’‘(‘[<E>{‘,‘<E>}]‘)‘|‘(‘<E>‘)‘
Пояснення позначень:
<P> — програма
<VD> — опис змінних
<FD> — опис функцій
<IT> — ідентифікатор типу
<WS> — wide space (Space, Enter, Tab)
<IV> — ідентифікатор змінної
<L> — букви
<NU> — цифри (десяткова система числення)
<IF> — ідентифікатор функції
<PD> — опис параметрів
<PL> — список параметрів
<PS> — типізація параметрів
<SS> — складний оператор
<S> — оператор
<E> — вираз
<D> — доданок
<M> — множник
<A> — атомарний вираз
Лістинг програми
F1.c
int fibb(int mode)
{
static int f1, f2, f3;
if (mode==0) {
f3=f1+f2;
f1=f2;
f2=f3;
} else {
f1=0;
f2=1;
}
return (f1);
}
extern K;
int get_rand()
{
return fibb(0)%K;
}
F2.c
extern x, y, z, ro, xx, yy;
extern V, W, U, K, dl, dm, de, M0, M, E0, E;
int P() // Put
{
x=get_rand();
y=get_rand();
z=get_rand();
ro=get_rand();
// cur_m = x*y*z*ro;
return 0;
}
int C() // Centre
{
return 0;
}
int R() // Rotare Ox
{
xx=y;
yy=z;
y=yy;
z=xx;
}
int T() // Rotare Oy
{
xx=x;
yy=z;
x=yy;
z=xx;
}
int A() // Accept
{
E0-=de;
M0=M0 + ro*min(dl,x)*y*z - dm;
V-=min(dl,x)*y*z;
x-=min(dl,x);
}
int D() // Drop
{
x=0;
return 0;
}
F3.c
int x, y, z, ro, xx, yy;
int V, W, U, K, dl, dm, de, M0, M, E0, E;
int swap()
{
int t;
t = xx;
xx = yy;
yy = t;
}
int min(int x, int y)
{
return x<y? x: y;
}
int get_x(int mode)
{
if (mode==-1) return 1000000000;
if (mode/3 == 0) return x;
if (mode/3 == 1) return y;
if (mode/3 == 2) return z;
}
int main()
{
// Initializing variables
V = 50;
W = 11;
U = 7;
K = 13;
dl = 1;
dm = 8;
de = 40;
M0 = 100;
M = 140;
E0 = 400;
E = 220;
// Workplace
fibb(1);
while (E0 > E && M0 < M && V!=0) {
P();
int minx;
minx = -1;
if (y<=W && z<=U && x<get_x(minx)) minx=0;
if (z<=W && y<=U && x<get_x(minx)) minx=1;
if (z<=W && x<=U && y<get_x(minx)) minx=2;
if (x<=W && z<=U && y<get_x(minx)) minx=3;
if (x<=W && y<=U && z<get_x(minx)) minx=4;
if (y<=W && x<=U && z<get_x(minx)) minx=5;
if (minx>0) {minx-=1; R();}
if (minx>1) {minx-=1; T();}
if (minx>2) {minx-=1; R();}
if (minx>3) {minx-=1; T();}
if (minx>4) {minx-=1; R();}
if (y<=W && z<=U) while (x*y*z*ro>0 && E0-de >= E && M0+(min(dl,x)*y*z*ro)-dm <= M && V-min(dl,x)*y*z>=0) A();
if (x>0) D();
}
// Returning
return 0;
}
