Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.03.2015, 17:45   #1
Adelia
Пользователь
 
Регистрация: 24.08.2014
Сообщений: 15
По умолчанию Олимпиадная задачка - найти K минимально близкое ( разницей сумм делителей + разность самих чисел) к заданному числу N

Всем здравствуйте.Помогите пожалуйста разобраться с задачей.Не знаю даже с чего начать ,подросте хоть какие-нибудь идеи.Заранее спасибо)
Вот условие:

В сказочной стране СВУД очень любят решать различные математические задачи. Не так давно в одном из университетов СВУД была придумана следующая задача. Пусть имеется некоторое натуральное число N и существует некоторое натуральное число K, отличное от N. Обозначим сумму всех делителей числа N через SN, а сумму всех делите-лей числа K через SK (в суммы SN и SK не входят сами числа N и K). Найдем модуль разно-сти N и K, и модуль разности SN и SK, . Само число K выбрано при этом таким образом, что сумма этих модулей является минимально возможной.
Например, пусть N = 18. Тогда SN = 21 (1+2+3+6+9 = 21). Число K, удовлетворяю-щее условиям задачи, будет равно 20. Действительно, SK = 22 (1+2+4+5+10 = 22). Поэтому . Для других чисел такая сумма будет больше 3, поэтому K = 20 – искомое число.
Оригинального решения такой задачи пока еще никто из жителей СВУД не пред-ложил. Помогите жителям СВУД найти решение этой увлекательной задачи.

Входные данные: В первой строке входного файла INPUT.TXT записано одно це-лое число N, причем 3 ≤ N ≤ 107.

Выходные данные: В выходной файл OUTPUT.TXT нужно вывести число K, удо-влетворяющее условиям задачи.
Дополнительные требования: время счета – не более 5 минут; при превышении от-веденного лимита времени будут назначены штрафные баллы.

Примеры
№ INPUT.TXT OUTPUT.TXT
1 900 1050
2 5040 5760
3 75600 81900
4 362880 372960
5 1000000 998900
Adelia вне форума Ответить с цитированием
Старый 17.03.2015, 18:16   #2
Adelia
Пользователь
 
Регистрация: 24.08.2014
Сообщений: 15
По умолчанию

Мне пришла идея,но не совсем получается ее реализовать.
Ясно,что K будет находиться недалеко от N , оно будет N/2<k<N*2
вот что получилось:
может я что упускаю,подскажите пожалуйста.

Код:
var j,min,N,K,Sn,Sk:longint;
    input,output:text;
procedure deliteli(a,s:longint);
 var j:integer;
 begin
 s:=0;
 for j:=1 to (a div 2) do
  if a mod j=0 then s:=s+j;
 end; 
begin
assign(input,'input.txt');
reset(input);
readln(input,n);
deliteli(N,Sn);
min:=10000000;
for j:=(n div 2) to (n*2) do begin
 deliteli(j,Sk);
 if ((abs(N-j)+abs(Sn-Sk))<=min) and (j<>N) then
          begin
          min:=abs(N-j)+abs(Sn-Sk);K:=j;
          end;
end; 
close(input);
assign(output,'output.txt');
rewrite(output);
writeln(output,K);
close(output);
end.
Adelia вне форума Ответить с цитированием
Старый 17.03.2015, 20:28   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Код:
procedure deliteli(a:longint; var s:longint);
N/2<k<N*2 от фонаря или есть логичные соображения?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 18.03.2015, 09:50   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Аватар
N/2<k<N*2 от фонаря или есть логичные соображения?
Adelia, присоединяюсь к вопросу. Поделитесь логикой вывода..

Цитата:
Код:
for j:=1 to (a div 2) do
и, на мой взгляд, немного сократить перебор поможет ограничение цикла до trunc( sqrt( a ) )
НО! На мой взгляд, для чисел до 10 миллионов (10^7) простой перебор не очень эффективен.
Тут хорошенько подумать надо...
Serge_Bliznykov вне форума Ответить с цитированием
Старый 18.03.2015, 10:16   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
немного сократить перебор поможет ограничение цикла до trunc( sqrt( a ) )
Не думаю, что это хорошо, 50 делитель 100, но серьёзно больше корня квадратного из 100

PS Если учитывать парные делители, то все будет Ok, так что я не прав
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 18.03.2015 в 10:40.
Аватар вне форума Ответить с цитированием
Старый 18.03.2015, 10:38   #6
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Не думаю, что это хорошо, 50 делитель 100, но серьёзно больше корня квадратного из 100
Вы правы!!

Я ошибся!! Такое ограничение допустимо ТОЛЬКО для простых чисел.
т.е. если до корня из A не было делителей (кроме единицы, конечно),
тогда больше делителей и не будет. (для проверки на простоту числа это подходит).
Но в данном случае, конечно, придётся перебирать до a div 2

а оценить время поможет такой тупо переборный код:
Код:
program testmax;

function sumdel( a : longint ):longint;
var sum, i : longint;
begin
  sum := 1;
  for i:=2 to (a div 2) do
    if (a mod i)=0 then sum := sum + i;
  sumdel := sum;
end;

var i, tmp, maxsum, imax : longint;
begin
   maxsum := -1;
   for i:=1 to 100000 {для проверки увеличить до 10000000 и запастись терпением} do begin 
     tmp := sumdel(i);
     if tmp>maxsum then begin
       maxsum := tmp;
       imax := i
     end; 
   end;
   WriteLn(' number ',imax,' has sum of dividers = ', maxsum);
end.
но, по моим прикидкам такой код будет работать около 15 минут...
т.е. это тупиковое направление для решения данной задачи...
Serge_Bliznykov вне форума Ответить с цитированием
Старый 18.03.2015, 11:02   #7
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Ниче не понял.. Ну делится 100 на 50 и что? Мы ж будем под два делителя брать..

Упс.. Заметил P.S
Пардон

А давайте так бахнем : посчитаем для всех n из 0..10^7..
Потом отсортируем.. И найдем бинарным наш..
За 10 часов просчитает..

Ах да.. На кнопку правка не попадаю(ибо гадкий планшет), поэтому склейте пжалста..

Последний раз редактировалось Serge_Bliznykov; 18.03.2015 в 13:14.
Poma][a вне форума Ответить с цитированием
Старый 18.03.2015, 11:12   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

А вот как себя ведет эта аликвотная сумма (термин в вики нашел) до n=1000. Очень похоже, что N/2<k<N*2 слишком большой интервал. А какой брать - вопрос
Изображения
Тип файла: jpg Безымянный.JPG (85.6 Кб, 112 просмотров)
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 18.03.2015, 11:24   #9
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

А интересно, насколько быстро можно из простых множителей получить сумму делителей
Poma][a вне форума Ответить с цитированием
Старый 18.03.2015, 12:15   #10
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
А давайте так бахнем : посчитаем для всех n из 0..10^7..
Потом отсортируем.. И найдем бинарным наш..
За 10 часов просчитает..
Чуть больше 6 минут без сортировки
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычислить произведение чисел, неравных заданному числу Z Hug Помощь студентам 4 12.11.2013 23:27
найти кол-во трехзначных чисел сумма простых делителей которых кратна 5 (на Делфи) anzorchik Помощь студентам 2 02.10.2011 16:18
Определить ближайший элемент массива к заданному числу wowan Паскаль, Turbo Pascal, PascalABC.NET 1 28.05.2011 23:21