2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача "квадратная страна"
Сообщение01.03.2015, 10:36 
Аватара пользователя

(Оффтоп)

В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась целым положительным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок.
Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 × 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», — сказал он. Сделка состоялась.
Найдите, какое количество квадратных свидетельств он получил.
Исходные данные
В единственной строке стоит целое положительное число N ≤ 60 000 — число квадриков, которое было у жителя.
Результат
В единственной строке стоит число свидетельств, полученных в результате сделки.
Пример: 344 | 3

2 день пытаюсь понять, почему у меня выходят не правильные ответы. Для 344 правильный, для 1, 2, 4 правильно, для 3 и 5 нет.

(Оффтоп)

Код:
#include<stdio.h>
#include<iostream>
#include<cmath>

using namespace std;

int minim[128];
int otvet = 1;

int count(double a, int min)
{
   for(double k = floor(sqrt(a)); k>0; k--)
   {
      if(a-k*k == 0)
         return 1;
      otvet +=1;
      /*printf("%lf", k);*/
      for(int i = 0; i<k; i++)
      {
         if(i*i == a-k*k)
         {
            return 1;
         }
      }
      count(k,otvet+1); return 1;
   }
}
int main()
{
   double a;
   scanf("%lf", &a);
   if(a == 2)
      printf("2");
   else
   {
   count(a, otvet);
   printf("%d", otvet);
   }
}

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 12:08 
Аватара пользователя
Извините, не тот код запостил
Код:
#include<stdio.h>
#include<iostream>
#include<cmath>

using namespace std;

int otvet = 1;

int count(double a, int min)
{
   for(double k = floor(sqrt(a)); k>0; k--)
   {
      if(a-k*k == 0)
         return 1;
      otvet +=1;
      /*printf("%lf", k);*/
      for(int i = 0; i<k; i++)
      {
         if(i*i == a-k*k)
         {
            return 1;
         }
      }
      count(k,otvet+1); return 1;
   }
}
int main()
{
   double a;
   scanf("%lf", &a);
   int k = floor(sqrt(a));
   if(a-k*k == 0)
      printf("1");
   else
   {
   count(a, otvet);
   printf("%d", otvet);
   }
}

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 16:52 
Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 17:18 
Аватара пользователя
venco в сообщении #984224 писал(а):
Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

Вы определенно правы, но мой код выдает 2 для 18. Похоже, что у меня неправильное решение не правильно работает.

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 17:35 
Dr.RichardFeynman в сообщении #984247 писал(а):
venco в сообщении #984224 писал(а):
Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

Вы определенно правы, но мой код выдает 2 для 18. Похоже, что у меня неправильное решение не правильно работает.
Это потому что у вас запрещены одинаковые квадраты.
Попробуйте $41 = 25+16$. У вас должно получиться $41 = 36+4+1$.
Собственно, конкретная ошибка не важна. Надо алгоритм менять.

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 18:27 
Аватара пользователя
venco в сообщении #984261 писал(а):
Dr.RichardFeynman в сообщении #984247 писал(а):
venco в сообщении #984224 писал(а):
Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

Вы определенно правы, но мой код выдает 2 для 18. Похоже, что у меня неправильное решение не правильно работает.
Это потому что у вас запрещены одинаковые квадраты.
Попробуйте $41 = 25+16$. У вас должно получиться $41 = 36+4+1$.
Собственно, конкретная ошибка не важна. Надо алгоритм менять.

Да, я понял
Спасибо

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 19:05 

(Оффтоп)

Dr.RichardFeynman, C++ язык распространённый и поддерживается потому тегом syntax, в котором синтаксис подсвечивается. Так что чуть лучше писать не [​code]...[​/code], а [​syntax lang="cpp"]...[​/syntax], и можно даже не писать, а выбрать в списке «Подсветка синтаксиса» C++, само вставится. :-)

 
 
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 19:16 
Аватара пользователя
arseniiv в сообщении #984331 писал(а):

(Оффтоп)

Dr.RichardFeynman, C++ язык распространённый и поддерживается потому тегом syntax, в котором синтаксис подсвечивается. Так что чуть лучше писать не [​code]...[​/code], а [​syntax lang="cpp"]...[​/syntax], и можно даже не писать, а выбрать в списке «Подсветка синтаксиса» C++, само вставится. :-)

(Оффтоп)

Виноват, не разобрался

 
 
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 21:33 
venco в сообщении #984261 писал(а):
Собственно, конкретная ошибка не важна. Надо алгоритм менять.

А какой алгоритм подойдёт в данном случае? Для большого массива чисел в некоторых случаях может найтись "удачное" совпадение - как его отловить?. Всё еще усложняется, если можно повторно использовать одни и те же цифры.

 
 
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 22:02 
Динамическое программирование - поиск всех возможных значений сумм из 1 квадрата, 2-х квадратов, и т.д.
Сложность:
$N\cdot R < N^{3\over2}$
где $R$ - результат.

(Оффтоп)

Кстати, какая оценка $R$ для всех чисел $<N$.
Как минимум $\ln N$, а то и даже $\ln\ln N$.

 
 
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 23:27 
Аватара пользователя
Alexu007 в сообщении #985688 писал(а):
А какой алгоритм подойдёт в данном случае?

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

-- 04.03.2015, 23:28 --

venco в сообщении #985699 писал(а):
Кстати, какая оценка $R$ для всех чисел $<N$.

Это Вы не о теореме о четырёх квадратах, случаем?

 
 
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 23:39 
Geen в сообщении #985734 писал(а):
venco в сообщении #985699 писал(а):
Кстати, какая оценка $R$ для всех чисел $<N$.

Это Вы не о теореме о четырёх квадратах, случаем?
Да. Как это я мог про неё забыть.

 
 
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 23:49 
Аватара пользователя
Кстати, для четвёртой степени график "забавно" выглядит...

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group