Алгоритм

[boomeer]

Не могу понять как решить такую задачу - у нас есть весы и какой то продукт весом x. Еще у нас есть грузики с весом 1,3,9,27 и тд по 1 штуке. Нужно определить сколько грузиков нужно использовать, чтобы сказать сколько весит х. Ну например, ввели х = 8. Значит нужно 2 грузика - 9 на одну чашку весов и 1 на другую

Вероятно, можно как то действовать через троичную систему счисления...

[_Ivana]

UPD оптимизировал немножко код

function Ivana_balance_3(V)

int = sum(V);

if int == 0
    V(1) = [];
    V
    m = abs(sum(V))
    return
end

m = 1;
while m < 2*abs(int)/3
    m = m*3;
end

V = [V, -sign(int)*m];

Ivana_balance_3(V);

Вызов

V = 3125;
Ivana_balance_3(V);

Результат

V =
       -2187        -729        -243          27           9          -3           1
m =
        3125

Положительные веса на чашку с грузом, отрицательные на другую. Разбирайтесь

[arseniiv]

boomeer в сообщении #625872 писал(а):

Вероятно, можно как то действовать через троичную систему счисления...

Ага. Есть такая особая волшебная троичная система с цифрами $\{-1, 0, 1\}$.

[_Ivana]

Убрал рекурсию и заменил простые циклы на лаконичные по записи но более долгие по вычислениям элементарные функции

int = 3125;
while int ~= 0
    g = - sign(int)*3^fix(log(2*abs(int))/log(3))
    int = int + g;
end

-2187
-729
-243
27
9
-3
1

[Pavia]

назодишь лучшее приближение вычитаешь. Считаем новое число как исходно данное его нам задали. Т.е реккурсивный алгоритм. В зависимости от знака кладёшь грузики на нужную сторону.

И учесть что если a<x<b. где a, b наиболее близки. Если a<x<2a то решентя ищется как х-a, а если
2a<x<=b то решение надо ещё проверить
x_new=b-x.

если х=2a то решения нет.

-- Вт окт 02, 2012 07:48:17 --

назодишь лучшее приближение вычитаешь. Считаем новое число как исходно данное его нам задали. Т.е реккурсивный алгоритм. В зависимости от знака кладёшь грузики на нужную сторону.

И учесть что если a<x<b. где a, b наиболее близки. Если a<x<2a то решентя ищется как х-a, а если
2a<x<=b то решение надо ещё проверить
x_new=b-x.

если х=2a то решения нет.

[ewert]

Используется синтаксис Pascal

{w - полный вес                }
{m - грузиков текущего номинала}
{n - полное количество грузиков}
n:=0;
while w>0 do begin
    m:=w mod 3;
    if m<>0 then n:=n+1;    {кладём грузик то ли направо, то ли налево}
    if m=2 then w:=w+1;     {если положили налево}
    w:=w div 3;
end;

(Я не помню, какие там функции в Матлабе реализуют целочисленное деление; какие-то есть.)

[boomeer]

ewert в сообщении #625953 писал(а):

Используется синтаксис Pascal

{w - полный вес                }
{m - грузиков текущего номинала}
{n - полное количество грузиков}
n:=0;
while w>0 do begin
    m:=w mod 3;
    if m<>0 then n:=n+1;    {кладём грузик то ли направо, то ли налево}
    if m=2 then w:=w+1;     {если положили налево}
    w:=w div 3;
end;

Спасибо! Элегантно.
А как бы сюда добавить ограничение на то, что на каждой чаше весов может быть не более 1'000'000 единиц?

[_Ivana]

Pavia в сообщении #625943 писал(а):

а если
2a<x<=b то решение надо ещё проверить
x_new=b-x.

если х=2a то решения нет.

Как нет? То есть, не все массы можно взвесить такими гирями? У меня получается все - что я делаю не так?

ewert в сообщении #625953 писал(а):

Я не помню, какие там функции в Матлабе реализуют целочисленное деление; какие-то есть.

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

boomeer в сообщении #625995 писал(а):

А как бы сюда добавить ограничение на то, что на каждой чаше весов может быть не более 1'000'000 единиц?

Вам написали несколько вариантов кодов и даже рассказали словами логику. Неужели не справитесь с введением ограничений?

[_Ivana]

А вообще, предлагаю автору решить пару простеньких подзадачек:
1) Доказать что любой целый вес можно взвесить данным набором гирь, с одной гирей каждой массы.
2) Посчитать максимальный вес, любое значение до которого можно взвесить $n$ первыми гирями. Подставить в эту формулу 1'000'000 и оценить результат

[Pavia]

_Ivana
Взвесь x=6

[_Ivana]

Pavia, 3 на чашку с грузом, 9 на другую. Сколько ещё взвесить? Не стесняйтесь, заказывайте побольше - у меня все равно компьютер быстро считает

[arseniiv]

Взвешиваемо любое целое число, т. к. я ничего не выдумал про систему счисления. Нормальная позиционная система, в ней можно представить любое действительное число, как и в обычной троичной.

[boomeer]

мой код вышел такой

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
    int n,ans=0,k=0;
    scanf("%d", &n);
    while (n>0)
    {
        if (n>1000000)
            {
                printf("Перевес");
                exit(0);
            }
        if ((n/(int)pow(3,k)%3)==1)
            {
                n-=pow(3,k);
                ans++;
            }
        else if ((n/(int)pow(3,k)%3)==2)
        {
            ans++;
            n+=pow(3,k);
        }
        k++;
    }
    printf("%d Ответ",ans);
}

-- Чт окт 04, 2012 09:08:08 --

Два новых вопроса.
1) На вход подают число $N<=100$;
Затем N строк по 4 числа - первые 3 координаты шаров, 4я радиус шара.
Нужно определить, есть ли два шара имеющих общую точку.

2)На вход подается число $N<=4000$.
Затем последовательность из N чисел, где каждое число $<= 100000$.
Нужно найти, сколько существует троек чисел $(i, j, k)$ таких, что:
$1 <= i < k < j <= N$
$k = (i + j) / 2$
$a_k = (a_i + a_j) / 2$

[boomeer]

С шарами решил, а тут не придумаю как ограничить перебор...

[boomeer]

Обе решил.
Другая - более интересная.
Некто расставил на шахматной доске кубики. Посмотрел на них прямо спереди и сказал слева направо сколько кубиков он видит (8 столбиков)
Затем посмотрел справа на них и тоже сказал сколько кубиков он видит, тоже справа налево.
Наша задача сказать, какое наименьшее кол-во кубиков могло быть на доске или сообщить некто, что он ошибся.

Например, для
1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0
Ответ 4;

А для
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 2
Следует оказать, что некто ошибся.