Составить вес (С++ или др.) Помощь в определении общего способа решения

[monsterkill]

Добрый день. Есть задачи для экзамена по профилю "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей".
Помогите определить, какого рода эти задачи, какими способами решаются.

Не знаю, с какой стороны подступиться. Каюсь, математика безвозвратно забыта. Вероятно предполагается написать ответ в виде кода, решающего эту задачу при заданных переменных. Код осилю сам, дайте хотя бы направление, куда идти)). (но если кто-то добрый напишет готовое решение, не откажусь).

Текст задач:

2. Составить вес. Даны натуральные числа а1, ... , а10. Предположим, что имеются 10
гирь ве сом а1, ... , а10. Обозначим через ck - число способов, которыми можно составить вес k, т.е. ck - это число решений уравнения
a1x1 + ... + a10x10 = k ,
где xi может принимать значение 0 или 1 (i = 1, ... , 10).
Получить c0, ... , c10.

3. Выплатить сдачу. Даны натуральные числа а1, ... , а6. Предположим, что имеются 6 видов монет достоинством а1, ..., а6. Обозначим через bk число способов, которыми можно выплатить сумму k, т. е. bk - это число решений уравнения
a1x1 + ... + a10x10 = k ,
где xi может принимать целые неотрицательные значения.
Получить b1, ... , b20.

4. Даны действительные числа x1, ... , x15, y1, ... , y15, r1, ... , r15. Выяснить, есть ли точка, принадлежащая всем кругам c1, ... , c15, где ci имеет центр с координатами xi, yi и радиус ri ( i= 1, ... , 15).

.. и подобные.
Спасибо.

[challengerr]

1. псевдокод

a[10]; n=0;
main(k)
{
for(xo=0;x0<2; x0++)
f(k,0+a0*x0,0);
}
f(k,s,i)
{
if (i==10) return;
for(xi=0;xi<2;xi++){
if (s+ai*xi == k) n++;
f(k, s+xi*ai,++i);}
}

Пусть задан круг с координатами центра (x1, y1) и радиусом r1 и круг с координатами центра (x2, y2) и радиусом r2. Расстояние между центрами вычисляется в декартовой прямоугольной системе координат как квадратный корень из выражения [ (x2-x1)^2 + (y2-y1)^2 ]. Если это расстояние равно r1 +r2, то имеется одна точка пересечения кругов. Если это расстояние больше r1+r2, то значит круги не пересекаются, а значит, если есть хоть один из наборов двух таких кругов, то значит точки, принадлежащей всем кругам нет.
Описание круга делается в виде структуры:

strict circle
{
float x;
float y;
float r;
};

Описание массива из 15 кругов делается объявлением

strict circle circle_set[15];

Рассматриваем все пары составленные из двух кругов

for(i=0;i<15;i++)
for(j=i+1;j<15;j++)
{
R=sqrt(pow((circle_set[j].x - circle_set[i].x),2) + pow((circle_set[j].y - circle_set[i].y), 2));
if (R < (circle_set[j].r + circle_set[i].r));
else
exit(); //нашлась точка, которая не принадлежит одной из пар кругов
}

[monsterkill]

Сообщение от challengerr

1. псевдокод

a[10]; n=0;
main(k)
{
for(xo=0;x0<2; x0++)
f(k,0+a0*x0,0);
}
f(k,s,i)
{
if (i==10) return;
for(xi=0;xi<2;xi++){
if (s+ai*xi == k) n++;
f(k, s+xi*ai,++i);}
}

Спасибо за лаконичный код.
Верно ли я понял, что (1.) сначала мы заходим в глубь рекурсии, складывая ai*xi при xi =0. Двигаясь вверх, мы обходим случаи xi=1.
2. Что вы имели ввиду под "return"? Это аварийный выход из цикла, или здесь следует описать движение на выходе из рекурсии, например

if (i==10) {--i; break;} //или что-то вроде

?
3. вместо if (i==10) должно быть if (i==9)? т.к а0*x0 мы уже прошли, верно?
4. n - это количество решений?
5.

Сообщение от monsterkill

Получить c0, ... , c10.

Требуется получить набор xi для каждого решения?

Сообщение от challengerr

Пусть задан круг...

А для такого случая как быть?

[challengerr]

Сообщение от monsterkill

Спасибо за лаконичный код.
Верно ли я понял, что (1.) сначала мы заходим в глубь рекурсии, складывая ai*xi при xi =0. Двигаясь вверх, мы обходим случаи xi=1.
2. Что вы имели ввиду под "return"? Это аварийный выход из цикла, или здесь следует описать движение на выходе из рекурсии, например

if (i==10) {--i; break;} //или что-то вроде

?
3. вместо if (i==10) должно быть if (i==9)? т.к а0*x0 мы уже прошли, верно?
4. n - это количество решений?
5.

Требуется получить набор xi для каждого решения?

n это количество способов, которым можно составить вес. xi принимает значения {0,1} поэтому в цикле делается перебор значений от 0 до 1. Return при i равном 10 для остановки рекурсии, так как иначе будет срыв стека из-за ухода на бесконечность.

Сообщение от monsterkill

А для такого случая как быть?

Если обозначить круги за a, b, c, то приведенный код подобный случай отрабатывает правильно, так как на рассмотрении круга a и b r дает равенство, поэтому происходит выход.

[monsterkill]

Сообщение от challengerr

Если обозначить круги за a, b, c, то приведенный код подобный случай отрабатывает правильно, так как на рассмотрении круга a и b r дает равенство, поэтому происходит выход.

Верно. Неудачная картинка. Вот:

Сообщение от challengerr

Return при i равном 10 для остановки рекурсии, так как иначе будет срыв стека из-за ухода на бесконечность.

Простите, не пойму, когда же мы переходим к xi=1.
Получается, вызывая f в цикле for, мы увеличиваем i, пока i !=10.
xi так и остаётся = 0 для каждого ai. Или я не совсем понимаю работу Return?

[challengerr]

Сообщение от monsterkill

Простите, не пойму, когда же мы переходим к xi=1.
Получается, вызывая f в цикле for, мы увеличиваем i, пока i !=10.
xi так и остаётся = 0 для каждого ai. Или я не совсем понимаю работу Return?

При возврате по рекурсии xi становится 1.

Сообщение от monsterkill

Верно. Неудачная картинка. Вот:

Значит мой алгоритм для решения является неправильным.

[challengerr]

В 3 задаче нужно тогда проверять области пересечения окружностей на пересечение полным попарным перебором. Область пересечения находится решением системы уравнений. Возьмите учебник по аналитической геометрии, например Ильина, Позняка.

[monsterkill]

Пришло такое решение.
После того, как мы определили, что круги 1 и 2, пересекаются,
1) находим точки пересечения А и В.
2) Для любого круга Z, который пересекается с 1 и 2, необходимо проверить пересечение с кругами 3 и 4 (центры А и В , радиусы = AB).
Если это условие выполняется, значит этот круг имеет общие точки с областью пересечения кругов 1 и 2
3) Идём дальше, теперь применяем пункты (1) и (2) для пар 1 и Z, 2 и Z, 1 и 2 и следующего круга.
4) и т.д



Попробую реализовать в коде.

[Poma][a]

Дык

t = точки пересечения(0, 1);
for (int i = 1; i < n; i++) 
  for (int j = i+1; j < n; j++) 
{ temp = точки пересечения(i, j); if (temp.first != t.first && temp.second != b.first) return false;
return true;

Осталась написать точки пересечения и радоваться, не?