2014 dxdy logo

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

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




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


13/04/14
133
Тюмень

(Оффтоп)

В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась целым положительным числом метров. Приобретая участок земли со стороной 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 
Аватара пользователя


13/04/14
133
Тюмень
Извините, не тот код запостил
Код:
#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 
Заслуженный участник


04/05/09
4582
Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

 Профиль  
                  
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 17:18 
Аватара пользователя


13/04/14
133
Тюмень
venco в сообщении #984224 писал(а):
Жадный алгоритм тут просто не работает.
Лучше $18 = 9+9$, чем $18 = 16+1+1$.
Используйте динамическое программирование.

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

 Профиль  
                  
 
 Re: Задача "квадратная страна"
Сообщение01.03.2015, 17:35 
Заслуженный участник


04/05/09
4582
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 
Аватара пользователя


13/04/14
133
Тюмень
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 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

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


13/04/14
133
Тюмень
arseniiv в сообщении #984331 писал(а):

(Оффтоп)

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 21:33 


24/05/09

2054
venco в сообщении #984261 писал(а):
Собственно, конкретная ошибка не важна. Надо алгоритм менять.

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

 Профиль  
                  
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 22:02 
Заслуженный участник


04/05/09
4582
Динамическое программирование - поиск всех возможных значений сумм из 1 квадрата, 2-х квадратов, и т.д.
Сложность:
$N\cdot R < N^{3\over2}$
где $R$ - результат.

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 23:27 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Alexu007 в сообщении #985688 писал(а):
А какой алгоритм подойдёт в данном случае?

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

-- 04.03.2015, 23:28 --

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

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

 Профиль  
                  
 
 Re: Задача "квадратная страна"
Сообщение04.03.2015, 23:39 
Заслуженный участник


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

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

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


01/09/13
4318
Кстати, для четвёртой степени график "забавно" выглядит...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group