Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

[C++] Срочно помогите с задачкой

19K
19 ноября 2007 года
H!RURG
23 / / 02.07.2007
Саша считает красивыми числа, десятичная запись которых не содержит других цифр, кроме 0 и k (1 ≤ k ≤ 9). Например, если k = 2, то такими числами будут 2, 20, 22, 2002 и т.п. Остальные числа Саше не нравятся, поэтому он представляет их в виде суммы красивых чисел. Например, если k = 3, то число 69 можно представить так: 69 = 33 + 30 + 3 + 3.

Однако, не любое натуральное число можно разложить в сумму красивых целых чисел. Например, при k = 5 число 6 нельзя представить в таком виде. Но если использовать красивые десятичные дроби, то это можно сделать: 6 = 5.5 + 0.5.

Недавно Саша изучил периодические десятичные дроби и начал использовать и их в качестве слагаемых. Например, если k = 3, то число 43 можно разложить так: 43 = 33.(3) + 3.(3) + 3 + 3.(3).

Оказывается, любое натуральное число можно представить в виде суммы положительных красивых чисел. Но такое разложение не единственно — например, число 69 можно также представить и как 69 = 33 + 33 + 3. Сашу заинтересовало, какое минимальное количество слагаемых требуется для представления числа n в виде суммы красивых чисел.

Требуется написать программу, которая для заданных чисел n и k находит разложение числа n в сумму положительных красивых чисел с минимальным количеством слагаемых.
Входные данные

Во входном файле INPUT.TXT записаны два натуральных числа n и k (1 ≤ n ≤ 109; 1 ≤ k ≤ 9).
Выходные данные

В выходной файл OUTPUT.TXT выведите разложение числа n в сумму положительных чисел, содержащих только цифры 0 и k, количество слагаемых в котором минимально. Разложение должно быть представлено в виде: n=a1+a2+...+am. Слагаемые a1, a2, ..., am должны быть выведены без ведущих нулей, без лишних нулей в конце дробной части. Запись каждого слагаемого должна быть такой, что длины периода и предпериода дробной части имеют минимально возможную длину.

Например, неправильно выведены числа: 07.7; 2.20; 55.5(5); 0.(66); 7.(0); 7. ; .5; 0.33(03). Их следует выводить так: 7.7; 2.2; 55.(5); 0.(6); 7; 7; 0.5; 0.3(30). Предпериод и период каждого из выведенных чисел должны состоять не более чем из 100 цифр. Гарантируется, что хотя бы одно такое решение существует. Числа ряда следует выводит в порядке неубывания. Выходной файл не должен содержать пробелов.


очень срочнонужно решение этой задачи

[COLOR=Red]Почитай правила форума Студентам. Название темы должно отражать суть вопроса, получаешь замечание, в следущий раз бан и закрытие темы. Модератор.[/COLOR]
19K
19 ноября 2007 года
H!RURG
23 / / 02.07.2007
Тут Примеры ввода и вывода

№ INPUT.TXT OUTPUT.TXT
1 69 3 69=3+33+33
2 6 5 6=0.5+5.5
3 10 9 10=9.(9)
602
20 ноября 2007 года
KPI Student
265 / / 16.12.2006
Просьба о помощи прочитана.
Конкретные вопросы есть?
Просьбы "решите мне задачу" эффективнее задавать в конторах. где их за деньги решают. На форумах, ИМХО, бесплатно помогают в случае возникновения четких вопросов.
19K
20 ноября 2007 года
H!RURG
23 / / 02.07.2007
Ну мне эту задачу нужно сдать учителю иначе он мне лабараторную не поставит. Мне Помошь нужна !
13K
21 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: H!RURG
Ну мне эту задачу нужно сдать учителю иначе он мне лабараторную не поставит. Мне Помошь нужна !


Это ж где такие задачки задают? Фраза "учитель" как-то у меня ассоциируется со школой... задачка интересная, чисто алгоритмическая, так что как будет время придумаю решение ;)

Кстати, задачу с вероятностью 99% сводится к задаче о размене монет

13K
22 ноября 2007 года
specter
113 / / 28.09.2007
Итак, решение готово :) Но вчера дома инета небыло, так что скину вечером ;)

Идея такая... покажу на примере... пусть у нас n = 95, k=7... нужно разделдить n на k
95/7 = 13.(571428)

Теперь разложим чтобы были только 0 и 1...
13.(571428) = 11.(111111) + 1.(110111) + 1.(110101) + 0.(110101) + 0.(110001) + 0.(010001) + 0.(010001) + 0.(000001)

Теперь нужно умножить полученную сумму на k и будет ответ ;)

95 = 77.(777777) + 7.(770777) + 1.(770707) + 0.(770707) + 0.(770007) + 0.(070007) + 0.(070007) + 0.(000007)
19K
23 ноября 2007 года
H!RURG
23 / / 02.07.2007
Я нашол код к этой задачке но учитель придирается тем что у меня не выводит не по убыванию если кто может помогите сразобратся с этим
плизз
Код:
#include <stdio.h>
#include <string.h>

int N,K;

#define size 100

int ansc[size];
char dig[1000],digc;

int main(void)
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    scanf("%d%d",&N,&K);

    memset(ansc,0,sizeof(ansc));

    if( (1000000000 == N) && (K==1) ) { printf("%d=%d\n",N,N); return 0; }

    __int64 q=N,base=100000000*K;
    int i,j;
   int cnt=0;
   for(j=0; j<size ;j++)
    {        ansc[j]+=q/base;
        cnt+=q/base; q%=base;   q*=10;} printf("%d=",N);
    while(cnt){digc=0;
        for(j=size-1;j>=9;j--) if ( ansc[j] ) break;
        j++;
       for(i=0;i<9;i++)
{if( ansc ) break;}
   memset(dig,0,sizeof(dig));
  if(i==9) dig[digc++]='0';
   for(;i<j;i++)
  {
         if( i==9 ) dig[digc++]='.';
        if( ansc ) { ansc--; dig[digc++]='0'+K; cnt--; }
       else dig[digc++]='0';
}
 dig[digc++]=0;
   for(i=1;i<20;i++) if( 0==memcmp(&dig[60],&dig[60+i],20)) break;
if(dig[80])
   {
 for(j=50;j>=0;j--) if( dig[j] != dig[j+i] ) break;
   j++;
    dig[j]=0;
     printf("%s",dig);
dig[j+i+i]=0;
printf("(%s)",&dig[i+j-1]);
}
else printf("%s",dig);
if(cnt) printf("+");
}printf("\n");
    return 0;
}
13K
25 ноября 2007 года
specter
113 / / 28.09.2007
Вот тебе решение:
Код:
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

void delenie(int n, const int &k, vector<int> &chislo, vector<int> &drob, vector<int> &period, int &max, int &dmax, int &pmax)
{
    vector<int> ost;
    dmax = 0;
    pmax = 0;
    max = 0;

    int tmp = n/k;
    while ( tmp )
    {
        chislo.push_back(tmp%10);
        if ( tmp%10 > max ) max = tmp%10;
        tmp /= 10;
    }

    n = n%k;
    if ( n!= 0 )
    {
        ost.push_back(n);
        while (n < k) n *=10;
    }
   
    while ( n != 0 )
    {
        if ( n%k == 0 )
        {
            drob.push_back(n/k);
            if (n/k > dmax) dmax = n/k;
            max = dmax > max ? dmax : max;
            n = 0;
        }
        else
        {
            for (tmp = 0; tmp < ost.size() && ost[tmp] != n%k; ++tmp) ;
           
            if (tmp == ost.size())
            {
                ost.push_back(n%k);
                drob.push_back(n/k);
                if (n/k > dmax ) dmax = n/k;
                n = n%k;
                while (n < k) n *=10;
            }
            else
            {
                drob.push_back(n/k);
                if (n/k > dmax ) dmax = n/k;
                max = dmax > max ? dmax : max;
               
                for (int i = tmp; i < drob.size(); ++i)
                {
                    if (drob > pmax) pmax = drob;
                    period.push_back(drob);
                }
                drob.resize(tmp);
                dmax = 0;
                for (int i = 0; i < drob.size(); ++i)
                    if (drob > dmax) dmax = drob;

                n = 0;
            }
        }
    }
}

void resolve(int n, int k, vector<string> &summ)
{
    vector<int> chislo;
    vector<int> drob;
    vector<int> period;
    int max, dmax, pmax;
   
    delenie(n,k, chislo, drob, period, max, dmax, pmax);

    summ.resize(max);


    for (int i = chislo.size()-1; i >=0 ; --i)
    {
        for (int j = 0; j < chislo; j++ )
            summ[j] += '0'+k;
    }

    if ( !drob.size() && !period.size() )
        return;

    for (int i = 0; i < max; ++i)
    if ( summ.empty() )
        summ+="0.";
    else
        summ+='.';

    for (int i = 0; i < drob.size(); ++i)
        for (int j = 0; j < max; ++j)
            if ( drob > j )
                summ[j] += '0'+k;
            else
                summ[j] += '0';

    if ( !period.size() )
    {
        int j;
        for (int i = 0; i < max; ++i)
        {
            for (j = summ.length()-1; summ[j] == '0'; --j);
            summ.resize(j+1);
        }
        return;
    }

    for (int i = 0; i < max; ++i)
        summ+='(';

    for (int i = 0; i < period.size(); ++i)
        for (int j = 0; j < max; ++j)
            if ( period > j )
                summ[j] += '0'+k;
            else
                summ[j] += '0';
   
    for (int i = 0; i < max; ++i)
    {
        int j;
        for (j = summ.length()-1; summ[j] == '0'; --j);
        if ( summ[j] == '(')
        {
            j--;
            for (; summ[j] == '0'; --j);
            if ( summ[j] != '.' ) ++j;
            summ.resize(j);
        }
    }

    for (int i = 0; i < max; ++i)
        summ+=')';
}

int main()
{
    vector<string> summ;

    FILE * f = fopen("input.txt", "r");
    freopen("output.txt","w",stdout);

    int N = 1, K = 1;

    while ( !feof(f) )
    {
        fscanf(f, "%d%d\n", &N, &K);
        resolve(N,K, summ);

        cout<<N<<" = ";
        int i;
        for (i = 0; i< summ.size()-1; ++i )
        cout<<summ.c_str() << " + ";
        cout<< summ.c_str()<<endl;

        summ.clear();
    }
    fclose(f);
    return 0;
}


Пример входных данных:
 
Код:
95 7
66 3
22 8
16 7
10 9
6 5
69 3


Пример выходных:
 
Код:
95 = 77.(777777) + 7.(770777) + 7.(770707) + 0.(770707) + 0.(770007) + 0.(070007) + 0.(070007) + 0.(000007)
66 = 33 + 33
22 = 8.88 + 8.88 + 0.88 + 0.88 + 0.88 + 0.8 + 0.8
16 = 7.(777777) + 7.(777707) + 0.(077707) + 0.(077707) + 0.(077700) + 0.(070700) + 0.(070700) + 0.(070000)
10 = 9.(9)
6 = 5.5 + 0.5
69 = 33 + 33 + 3
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог