Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [c]Поиск чисел Армстронга длинной не более n

Автор: Kurganec 12.3.2009, 13:39

Всем здравствуйте.

Я участвую в олимпиаде по информатике на сайте http://olymp.ifmo.ru

задача такова:

Код


Число Армстронга — такое число из k цифр, для которого сумма k-х степеней его цифр равна самому числу, например: 153=13+53+33. Надите 5 наибольших чисел Армстронга, состоящих не более чем из n цифр. Программа должна считать выходые данные из файла input.txt и вывести результат в файл output.txt
Формат входного файла.

Входной файл содержит целое число n (1≤n≤5).
Формат выходного файла.

Выведите в выходной файл 5 наибольших чисел Армстронга в порядке возрастания.

Может быть и не стоило перебирать все числа, но вот что у меня получилось:

Код


#include <iostream>
#include "math.h"
using namespace std;
bool armstrong(int value);

int main()
{
    FILE * fi,*fo;
    int n,i,j;
    int a[5]={0,0,0,0,0};
    fi=fopen("input.txt","r");
    fo=fopen("output.txt","w");
    fscanf(fi,"%i",&n);
        for (i=1;(double)i<pow(10,n);i++){
        if (armstrong(i)){
            a[0]=a[1];
            a[1]=a[2];
            a[2]=a[3];
            a[3]=a[4];
            a[4]=i;
        }

    }
    for (i=0;i<4;i++) fprintf(fo,"%i ",a[i]);
    fprintf(fo,"%i",a[4]);



    fclose(fi);
    fclose(fo);

    return 0;
}

bool armstrong(int value){
    int tmp=value,s=0;
    int dl=0;
    while(value>0){
        value=value/10;
        dl++;
    }
    value=tmp;
    while (value>0){
        s+=pow(value%10,dl);
        value=value/10;
    }
    if (s==tmp) return 1;
    else return 0;

}

и впринцепе она работает правильно, однако она не засчитывается :"неверный ответ".

буду признателен за коментарии , альтернативные решения.

ps:проверял программу по этим материаллам - http://mathworld.wolfram.com/NarcissisticNumber.html

Автор: zim22 12.3.2009, 16:11

примените алгоритмы оптимизации. нет смысла перебирать все числа в лоб.
http://acmp.ru/article.asp?id_text=198