Задаци: Генерисање свих могућности¶
Алгоритми и програми у програмском језику C: Генерисање свих могућности.
Бројеви у датој основи¶
Прочитај текст задатка.
На сваком од три места могуће је исписати било коју цифру од \(0\) до \(b-1\). Стога решење можемо једноставно постићи помоћу три угнежђене петље - по једну за сваку од три цифре. Тројке цифара ће бити лексикографски растући уређене, што ће тачно одговарати редоследу бројева по величини, како се тражи у задатку.
Пошто ће се користити и основе веће од \(10\), потребно је да направимо и петљу која ће на основу нумеричке вредности цифре одредити карактер који представља ту цифру. Имплементација те петље захтева баратање са карактерским типом података.
Ако је вредност цифре мања од \(10\), карактер добијамо тако што саберемо ASCII кôд карактера
0
са вредношћу цифре.Ако је вредност цифре већа од \(10\), карактер добијамо тако што саберемо кôд карактера
a
са вредношћу цифре умањеном за 10.
Рецимо и да се у овом задатку заправо врши генерисање и исписивање свих варијација са понављањем дужине \(3\) са \(b\) елемената.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int b;
scanf("%d", &b);
for (int c2 = 0; c2 < b; c2++)
for (int c1 = 0; c1 < b; c1++)
for (int c0 = 0; c0 < b; c0++)
printf("%c%c%c\n", c2 < 10 ? '0' + c2 : 'a' + (c2 - 10),
c1 < 10 ? '0' + c1 : 'a' + (c1 - 10),
c0 < 10 ? '0' + c0 : 'a' + (c0 - 10));
return 0;
}
Варијације тројки¶
Прочитај текст задатка.
У задатку се тражи набрајање свих варијација без понављања дужине 3 од \(n\) елемената. Најлакши начин да се оне наброје је да се употребе три угнежђене петље - по једна за сваког од три другара. Бројач сваке петље (обележимо их са \(d_1\), \(d_2\) и \(d_3\)) узима редом вредности од \(0\) до \(n\). Ако би се у телу унутрашње петље вршио испис вредности променљивих, излистале би се све варијације (па и оне са понављањем). Да би се избегло понављање, потребно је пре исписа проверити да ли у вредности све три променљиве различите тј. да ли важи да је \(d_1\neq d_2\) и \(d_1\neq d_3\) и \(d_2\neq d_3\). Приметимо да се овде заправо ради о филтрирању, тј. издвајању само оних елемената који задовољавају неко дато својство. Услов \(d_1\neq d_2\) има смисла проверити пре него што се уопште уђе у трећу петљу.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
for (int d1 = 0; d1 <= n; d1++)
for (int d2 = 0; d2 <= n; d2++)
if (d1 != d2)
for (int d3 = 0; d3 <= n; d3++)
if (d1 != d3 && d2 != d3)
printf("%d %d %d\n", d1, d2, d3);
return 0;
}
Мали лото¶
Прочитај текст задатка.
Већ је у тексту задатка наглашено да се у овом задатку тражи исписивање свих комбинација (пошто су у игри лото сви бројеви различити, ради се о комбинацијама без понављања).
Најједноставније решење подразумева три угнежђене петље, по једну за сваку од три лоптице. Спољашња петља набрајаће редом бројеве на првој лоптици, средња на другој, а унутрашња на трећој, при чему су лоптице сортиране растући, како се тражи у тексту задатка. Стога бројач средње петље увек мора бити већи од бројача спољашње, а бројач унутрашње петље увек мора бити већи од бројача средње петље. Зато границе за прву бројачку променљиву \(b_1\) можемо поставити на \(1\) до \(n\), средњу \(b_2\) на \(b_1+1\) до \(n\), а унутрашњу \(b_3\) на \(b_2+1\) до \(n\). Заправо, горње границе су мало мање (за спољашњу је то \(n-2\), а средњу \(n-1\)), међутим, и за границе \(n\) програм ће радити коректно, јер ће нека од унутрашњих петљи бити празна (на пример, за \(b_1=n\), \(b_2\) креће од \(n+1\) и траје док је \(b_2\leq n\), што је у самом старту нарушено).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
for (int b1 = 1; b1 <= n; b1++)
for (int b2 = b1 + 1; b2 <= n; b2++)
for (int b3 = b2 + 1; b3 <= n; b3++)
printf("%d %d %d\n", b1, b2, b3);
return 0;
}
Коцкице за јамб¶
Прочитај текст задатка.
Ако са \(a\), \(b\) и \(c\) обележимо бројеве који су добијени на три коцкице важи да је \(a+b+c=x\), и да је \(1\leq a\leq 6\), \(1\leq b\leq 6\) и \(1\leq c\leq 6\). Проблем разлагања броја на збир неколико бројева назива се партиционисање тј. проналажења партиција броја. У овом случају разматрамо партиције дужине \(3\) (партиције на тачно три сабирка).
Наивно решење је да се помоћу три угнежђене петље наброје све могућности од \(1\) до \(6\) за \(a\), \(b\) и \(c\) и да се у телу унутрашње петље проверава да ли је \(a+b+c=x\).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x;
scanf("%d", &x);
for (int a = 1; a <= 6; a++)
for (int b = 1; b <= 6; b++)
for (int c = 1; c <= 6; c++)
if (a + b + c == x)
printf("%d %d %d\n", a, b, c);
return 0;
}
Бољи приступ је испробавати само све могућности за \(a\) и \(b\), а онда израчунавати \(c\) као \(x-a-b\) и проверавати да ли добијени резултат припада интервалу од \(1\) до \(6\).
Пажљивијом анализом можемо границе у петљама додатно оптимизовати, али пошто је укупан број могућности мали и ово решење је сасвим довољно ефикасно.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x;
scanf("%d", &x);
for (int a = 1; a <= 6; a++)
for (int b = 1; b <= 6; b++)
{
int c = x - a - b;
if (1 <= c && c <= 6)
printf("%d %d %d\n", a, b, c);
}
return 0;
}
Комбинације поена¶
Прочитај текст задатка.
Једно решење је да помоћу три угнежђене петље испитамо све могућности за број кошева са три поена (\(t\)), број кошева са два поена (\(d\)) и број кошева за један поен (\(j\)). Ако је број поена \(p\), границе ових променљивих веома грубо можемо одредити ако приметимо да број кошева са 1 поеном \(j\) може имати вредности целих бројева од 0 до \(p\), пошто мора да важи да је \(2\cdot d\leq p\), број кошева са 2 поена \(d\) може имати вредности целих бројева од 0 до \(\left\lfloor{\frac{p}{2}}\right\rfloor\), тј. до вредности целобројног количника бројева \(p\) и \(2\), а пошто мора да важи да је \(3\cdot t\leq p\), број кошева са 3 поена може имати вредности од 0 до \(\left\lfloor{\frac{p}{3}}\right\rfloor\).
Због траженог редоследа приказивања прво фиксирамо број \(t\) узимајући све могуће вредности од најмање (то је 0) до највеће (то је \(\left\lfloor{\frac{p}{3}}\right\rfloor\)), па затим број (\(d\)) од најмање вредности (то је 0) до највеће (то је \(\left\lfloor{\frac{p}{2}}\right\rfloor\)), и на крају број кошева са 1 поеном (\(j\)) од најмање вредности (то је 0) до највеће (то је \(p\)). У телу унутрашње петље проверавамо да ли је укупан број поена једнак вредности \(p\) (тј. проверавамо да ли је услов \(3\cdot t+2\cdot d+j=p\) испуњен).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int p;
scanf("%d", &p);
for (int t = 0; t <= p / 3; t++)
for (int d = 0; d <= p / 2; d++)
for (int j = 0; j <= p; j++)
if (3 * t + 2 * d + j == p)
printf("%d %d %d\n", t, d, j);
return 0;
}
Мало прецизнијом анализом можемо добити ефикаснији програм. Наиме, горњу границу променљиве \(t\) одређујемо из услова \(3\cdot t\leq p\) и добијамо вредност \(\left\lfloor{\frac{p}{3}}\right\rfloor\). Пошто мора да важи да је \(3\cdot t+2\cdot d\leq p\), за фиксирану вредност \(t\), границу за променљиву \(d\) можемо одредити као \(\left\lfloor{\frac{p-3\cdot t}{2}}\right\rfloor\). Такође, ако су познате вредности \(t\), \(d\) и \(p\), из услова \(3\cdot t+2\cdot d+j=p\) можемо израчунати да је \(j=p-3\cdot t-2\cdot d\), чиме избегавамо унутрашњу (трећу) петљу и непотребно испитивање различитих нетачних вредности за \(j\).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int p;
scanf("%d", &p);
for (int t = 0; t <= p / 3; t++)
for (int d = 0; d <= (p - 3 * t) / 2; d++)
{
int j = p - (3 * t + 2 * d);
printf("%d %d %d\n", t, d, j);
}
return 0;
}
Напоменимо и да није неопходно било израчунавати експлицитно горње границе, и итерација може бити контролисана оригиналним условима.
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int p;
scanf("%d", &p);
for (int t = 0; 3 * t <= p; t++)
for (int d = 0; 3 * t + 2 * d <= p; d++)
{
int j = p - (3 * t + 2 * d);
printf("%d %d %d\n", t, d, j);
}
return 0;
}
Цикличне пермутације¶
Прочитај текст задатка.
Потребно је за свако \(i\) која узима вредности од 1 до \(n\) приказати низ бројева облика \(i,i+1,\ldots,n,1,2,\ldots,i-1\).
Задатак можемо решити петљом у којој коришћењем бројачке променљиве \(i\) која узима вредности од 1 до \(n\), прво прикажемо једном петљом бројеве од \(i\) до \(n\), а затим другом петљом бројеве од 1 до \(i-1\).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
printf("%d ", j);
for (int j = 1; j < i; j++)
printf("%d \n", j);
}
return 0;
}
Приметимо да бројеве \(i,i+1,\ldots,n,1,2,\ldots,i-1\) можемо приказати у једној петљи, увећавањем бројачке променљиве редом за \(0,1,\ldots,n-1\) и коришћењем остатка при дељењу са \(n\) (пошто петља креће од 1, а не од 0, од збира \(i\) и \(j\) потребно је одузети 1, пронаћи остатак, а затим додати 1).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < n; j++)
printf("%d ", (i + j - 1) % n + 1);
printf("\n");
}
return 0;
}
Такође, у унутрашњој петљи можемо водити посебну променљиву која чува вредност која се исписује. Ту променљиву постављамо на вредност \(i\) и након сваког исписа је увећавамо за 1, при чему проверавамо да ли је након увећања вредност већа од \(n\). Ако јесте, враћамо је на вредност \(1\).
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int p = i;
for (int j = 1; j <= n; j++)
{
printf("%d ", p);
p++;
if (p > n)
p = 1;
}
printf("\n");
}
return 0;
}
Троуглови целобројних страница, задатог обима¶
Прочитај текст задатка.
Природни бројеви \(a\), \(b\) и \(c\) представљају дужине страница троугла ако и само ако су позитивни и задовољавају неједнакост троугла. На основу неједнакости троугла свака од страница троугла \(a\), \(b\) и \(c\) мора бити мања од збира друге две.
Са друге стране, услов неједнакости троугла чини анализу мало компликованијом. Још једна од разлика је то што се у овом задатку тражи да странице буду уређене по величини.
Наивно решење у три угнежђене петље проверава све могуће вредности за дужине страница (природне бројеве између \(1\) и \(O\)) и у телу унутрашње петље проверава да ли бројеви у збиру дају дати обим, да ли задовољавају тражени поредак и да ли су испуњене све три неједнакости троугла. Ако је све то испуњено, пронађен је исправан троугао и исписују се његове дужине страница.
Мало паметније решење користи чињеницу да из услова \(b\geq a\) петља која набраја могуће дужине странице \(b\) може да крене од \(a\) уместо од \(1\), као и чињеницу да петља за \(c\) није потребна јер се из услова \(O=a+b+c\), дужина \(c\) може једнозначно израчунати када су дате дужине \(a\) и \(b\).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int o;
scanf("%d", &o);
for (int a = 1; a <= o - 2; a++)
{
for (int b = a; b <= o - 2; b++)
{
int c = o - a - b;
if (a < b + c && b < a + c && c < a + b && 1 <= a && a <= b && b <= c)
printf("%d %d %d\n", a, b, c);
}
}
return 0;
}
Ипак, крајње решење је много боље и од овога. Пронаћићемо услове који су еквивалентни условима \(1\leq a\leq b\leq c\), \(O=a+b+c\) и \(a>b+c\), \(b>a+c\) и \(c>a+b\), који ће нам омогућити да направимо набрајање свих могућности без потребе за икаквом додатном провером сваке од њих унутар кода. Нагласимо да је у том случају потребно доказати еквивалентност између две групе услова - чињеница да из оригиналних услова следе изведни, који у програму важе на основу његове конструкције гарантују да ће сваки троугао који задовољава оригиналне услове бити набројан, док чињеница да из изведених услова следе оригинални гарантује да ће све тројке које су набројане одговарати неком траженом троуглу.
Услов да је нека страница мања од збира друге две еквивалентан је услову да је она мања од полуобима троугла. Заиста, \(a<b+c\) еквивалентно је услову \(a+a<a+b+c\) тј. \(a<\frac{a+b+c}{2}\) тј. \(a<\frac{O}{2}\).
Ако је \(n\) цео број, услов \(n<x\) еквивалентан је услову \(n<\left\lceil{x}\right\rceil\). Заиста, важи да је \(\left\lceil{x}\right\rceil-1<x\leq\left\lceil{x}\right\rceil\), па из \(n<x\) лако следи \(n<\left\lceil{x}\right\rceil\). Са друге стране, пошто је \(n\) цео број, ако је \(n<\left\lceil{x}\right\rceil\), који је такође цео број, тада је \(n\leq\left\lceil{x}\right\rceil-1\). Пошто је \(\left\lceil{x}\right\rceil-1<x\), важи да је \(n<x\).
На основу до сада реченог, неједнакост \(a<b+c\) еквивалентна је неједнакости \(a<\left\lceil{\frac{O}{2}}\right\rceil\). Број \(\left\lceil{\frac{O}{2}}\right\rceil\) једнак је броју \(\left\lfloor{\frac{O+1}{2}}\right\rfloor\).
Ако су познатe дужине страница \(a\) и \(b\), дужина странице \(c\) се израчунава као \(O-a-b\). По условима задатка треба да важи \(a\leq b\leq c\). Услов \(b\leq c\) еквивалентан је услову \(b\leq O-a-b\) тј. \(2b\leq O-a\) тј. \(b\leq\frac{O-a}{2}\).
Ако је \(n\) цео број, услов \(n\leq x\) еквивалентан је услову \(n\leq\left\lfloor{x}\right\rfloor\). Заиста, важи да је \(\left\lfloor{x}\right\rfloor\leq x<\left\lfloor{x}\right\rfloor+1\). Дакле, ако је \(n\leq\left\lfloor{x}\right\rfloor\) тада је сигурно и \(n\leq x\). Са друге стране, ако је \(n\leq x\) тада је \(n<\left\lfloor{x}\right\rfloor+1\), па је, пошто су и \(n\) и \(\left\lfloor{x}\right\rfloor\) цели бројеви, \(n\leq\left\lfloor{x}\right\rfloor\).
На основу овога важи да је услов \(b\leq c\) eквивалентан услову \(b\leq\left\lfloor{\frac{O-a}{2}}\right\rfloor\).
Ако су испуњени услови \(a\geq 1\) и \(b\leq c\), тада важи да је \(b\leq c<1+c\leq a+c\), тако да је аутоматски испуњен и услов \(b<a+c\).
Услов \(c<a+b\) еквивалентан је услову \(O-a-b<a+b\) тј. \(O-2a<2b\), тј. \(b>\frac{O-2a}{2}\).
Ако је \(n\) цео број, услов \(n>x\) еквивалентан је услову \(n>\left\lfloor{x}\right\rfloor\). Заиста, важи да је \(\left\lfloor{x}\right\rfloor\leq x<\left\lfloor{x}\right\rfloor+1\). Дакле, ако је \(n>x\) тада је сигурно и \(n>\left\lfloor{x}\right\rfloor\). Са друге стране, ако је \(n>\left\lfloor{x}\right\rfloor\), пошто су оба броја цела, важи да је \(n\geq\left\lfloor{x}\right\rfloor+1\). Међутим, пошто је \(\left\lfloor{x}\right\rfloor+1>x\), важи да је \(n>x\).
На основу реченог, услов \(c<a+b\) еквивалентан је услову \(b>\left\lfloor{\frac{O-2a}{2}}\right\rfloor\), а пошто је \(b\) цео број, ово је еквиваленто услову \(b\geq\left\lfloor{\frac{O-2a}{2}}\right\rfloor+1\). Зато је конјункција услова \(b\geq a\) и \(c<a+b\) еквивалентна услову да је \(b\geq\max{(a,\left\lfloor{\frac{O-2a}{2}}\right\rfloor+1)}\).
Дакле, конјункција услова \(1\leq a\leq b\leq c\) и \(a<b+c\), \(b<a+c\) и \(c<a+b\), \(O=a+b+c\) еквивалентна је конјункцији услова \(1\leq a<\left\lfloor{\frac{O+1}{2}}\right\rfloor\) и \(\max{(a,\left\lfloor{\frac{O-2a}{2}}\right\rfloor+1)}\leq b\leq\left\lfloor{\frac{O-a}{2}}\right\rfloor\) и \(c=O-a-b\).
Дакле, страница \(a\) може узети све вредности веће и једнаке \(1\) које су строго мање од броја \(\left\lfloor{\frac{O+1}{2}}\right\rfloor\), док за свако фиксирано \(a\) страница \(b\) може узети све вредности веће или једнаке \(\max{(a,\left\lfloor{\frac{O-2a}{2}}\right\rfloor+1)}\) и мање или једнаке од \(\left\lfloor{\frac{O-a}{2}}\right\rfloor\).
На основу свега реченог, програм се веома лако имплементира. У спољашњој петљи
мења се променљива a
, у унутрашњој b
, променљива c
се израчунава као
разлика обима и збира страница a
и b
и у сваком кораку се исписује тражена
тројка a
, b
, c
.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int o;
scanf("%d", &o);
for (int a = 1; a < (o + 1) / 2; a++)
{
for (int b = (a > ((o - 2 * a) / 2 + 1) ? a : ((o - 2 * a) / 2 + 1)); b <= (o - a) / 2; b++)
{
int c = o - a - b;
printf("%d %d %d\n", a, b, c);
}
}
return 0;
}