Интегральные треугольники и интегральные медианы

15

Рассмотрим треугольник ABC, где каждая сторона имеет целочисленную длину ( целочисленный треугольник ). Определить медиану из ABC быть отрезок от вершины до середины противоположной стороны. На рисунке ниже сегменты красной линии представляют медианы. Обратите внимание, что любой данный треугольник имеет три медианы.

triangle_medians

Пусть n будет некоторым положительным целым числом. Сколько невырожденных интегральных треугольников с длиной каждой стороны, меньшей или равной n, имеют хотя бы одну интегральную медиану?

Вызов

Напишите программу для вычисления количества интегральных треугольников с хотя бы одной интегральной медианой для данной максимальной длины стороны n . Порядок длин сторон не имеет значения, т.е. <6,6,5> представляет тот же треугольник, что и <5,6,6>, и должен учитываться только один раз. Исключите вырожденные треугольники, такие как <1,2,3>.

счет

Наибольшее число n, для которого ваша программа может сгенерировать количество треугольников за 60 секунд на моей машине, - это ваш результат. Программа с наибольшим количеством очков выигрывает. Моя машина Sony Vaio SVF14A16CLB, Intel Core i5, 8 ГБ оперативной памяти.

Примеры

Пусть Т ( Н ) быть программой с входным N .

T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34

Обратите внимание, что T (1) = T (2) = T (3) = T (4) = T (5) = 0, потому что никакая комбинация целых сторон не даст интегральной медианы. Однако, как только мы дойдем до 6, мы увидим, что одна из медиан треугольника <5,5,6> равна 4, поэтому T (6) = 1.

Также обратите внимание, что T (22) является первым значением, при котором двойной счет становится проблемой: треугольник <16,18,22> имеет медианы 13 и 17 (и 2sqrt (85)).

Вычисление медиан

Медианы треугольника можно рассчитать по следующим формулам:

введите описание изображения здесь

введите описание изображения здесь

введите описание изображения здесь

Current top score: Sp3000 - 7000 points - C
Николас Сиплис
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Дверная ручка

Ответы:

7

C, грубая сила - n = 6080

Это скорее базовый уровень, чем серьезный соперник, но, по крайней мере, все должно начаться.

n = 6080 - это столько же, сколько я получил за минуту работы на моем собственном компьютере, то есть MacBook Pro с Intel Core i5. Результат, который я получил для этого значения:

15041226

Кодекс чисто грубая сила. Он перечисляет все треугольники в пределах ограничения по размеру и проверяет условие:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static inline int isSquare(int v) {
    int s = (int)(sqrtf((float)v) + 0.5f);
    return s * s == v;
}

static inline int isMedian(int v) {
    return v % 4 == 0 && isSquare(v / 4);
}

int main(int argc, char* argv[]) {
    int n = atoi(argv[1]);
    int nTri = 0;
    int a, b, c;

    for (c = 1; c <= n; ++c) {
        for (b = (c + 1) / 2; b <= c; ++b) {
            for (a = c - b + 1; a <= b; ++a) {
                if (isMedian(2 * (b * b + c * c) - a * a) ||
                    isMedian(2 * (a * a + c * c) - b * b) ||
                    isMedian(2 * (a * a + b * b) - c * c)) {
                    ++nTri;
                }
            }
        }
    }

    printf("%d\n", nTri);

    return 0;
}
Рето Коради
источник
В зависимости от компилятора вы можете получить более быстрое + лучшее округление до ближайшего от использования lrintf()или (int)roundf()вместо добавления 0,5f и использования усечения по умолчанию. Однако иногда вам нужно использовать -ffast-mathего для компиляции в одну cvtss2siинструкцию. gcc inline lrintf()и sqrtfonly only -fno-math-errno, так что вы получите эффективный asm: godbolt.org/g/E3hncQ . (Я использовал, -march=ivybridgeпотому что это процессор ОП). С помощью -ffast-mathclang превращает sqrt в итерацию rsqrt + Ньютона; ИДК, если это победа.
Питер Кордес
К сожалению, обычно нет roundf. Используйте (int)nearbyintf()if lrintf(), не встроенный, потому что он использует текущий режим округления вместо определенного странного. stackoverflow.com/questions/37620659/…
Питер Кордес
6

С, около 6650 6900

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

static inline int is_square(int n) {
    if ((n&2) != 0 || (n&7) == 5 || (n&11) == 8) {
        return 0;
    }

    int s = (int) (sqrtf((float) n) + 0.5f);
    return (s*s == n);
}

int main(int argc, char **argv) {
    int n = atoi(argv[1]);
    int count = 0;

    for (int a = 1; a <= n; ++a) {
        if (a&1) {
            for (int b = (a+1)/2; b <= a; ++b){
                if (b&1) {
                    for (int c = a-b+2; c <= b; c += 2) {
                        if (is_square((a*a + b*b)/2 - (c*c)/4)) {
                            ++count;
                        }
                    }
                } else {
                    for (int c = a-b+2; c <= b; c += 2) {
                        if (is_square((a*a + c*c)/2 - (b*b)/4)) {
                            ++count;
                        }
                    }
                }
            }
        } else {
            for (int b = (a+1)/2; b <= a; ++b){
                if (b&1) {
                    for (int c = a-b+2; c <= b; c += 2) {
                        if (is_square((b*b + c*c)/2 - (a*a)/4)) {
                            ++count;
                        }
                    }
                } else {
                    for (int c = a-b+2; c <= b; c += 2) {
                        if (is_square((b*b + c*c)/2 - (a*a)/4) ||
                            is_square((c*c + a*a)/2 - (b*b)/4) ||
                            is_square((a*a + b*b)/2 - (c*c)/4)) {
                            ++count;
                        }
                    }
                }
            }
        }
    }

    printf("%d\n", count);
    return 0;
}

Я не очень часто использую C, но с учетом продолжающейся арифметики это казалось хорошим выбором языка. Основной алгоритм - грубая сила, как ответ @ RetoKoradi , но с несколькими простыми оптимизациями. Я не уверен, что наши значения сопоставимы, потому что компьютер @ RetoKoradi, кажется, быстрее, чем мой.

Основная оптимизация - полностью обойти % 4проверку. Целочисленный квадрат n*nравен 0 или 1 по модулю 4, в зависимости от того n, равен ли он 0 или 1 по модулю 2. Таким образом, мы можем взглянуть на все возможности для (x, y, z) % 2:

x%2  y%2  z%2    (2*(x*x+y*y) - z*z) % 4
----------------------------------------
 0    0    0              0
 0    0    1              3
 0    1    0              2
 0    1    1              1
 1    0    0              2
 1    0    1              1
 1    1    0              0
 1    1    1              3

Удобно, что нужно рассмотреть только два случая: (0, 0, 0)и (1, 1, 0), учитывая первые две стороны a, b, соответствует третьей стороне, cимеющей четность a^b:

 a%2   b%2         c%2 must be
 -----------------------------
  0     0               0
  0     1               1
  1     0               1
  1     1               0

a^bимеет тот же паритет a-b, что и вместо поиска c = a-b+1и увеличения на 1 с, это позволяет нам искать c = a-b+2и подниматься на 2 с.

Другая оптимизация связана с тем, что в данном (1, 1, 0)случае нам нужно вызывать is_square только один раз, так как работает только одна перестановка. Это особый случай в коде путем развертывания поиска.

Другая включенная оптимизация - просто быстрый сбой в is_squareфункции.

Компиляция была сделана с -std=c99 -O3.

(Спасибо @RetoKoradi за указание на то, что 0.5in_square должен быть 0.5fво избежание двойного преобразования.)

Sp3000
источник
1
Очень незначительное, но вы можете использовать 0.5fвместо 0.5в is_square(). 0.5является константой типа double, так что выражение произведет двойное значение при добавлении 0.5, в том числе преобразования типа из floatк doubleдля другого термина.
Рето Коради
@RetoKoradi Ах, спасибо - это было на удивление не второстепенно f, на самом деле.
Sp3000 15.07.15
2

Феликс, неизвестно

fun is_square(v: int) => let s = int$ sqrt$ v.float + 0.5f in s*s == v;
fun is_median(v: int) => v % 4 == 0 and (v/4).is_square;

proc main() {
    n := int$ System::argv 1;
    var ntri = 0;

    for var c in 1 upto n do
        for var b in (c+1)/2 upto c do
            for var a in c - b + 1 upto b do
                if is_median(2*(b*b+c*c)-a*a) or
                   is_median(2*(a*a+c*c)-b*b) or
                   is_median(2*(a*a+b*b)-c*c) do ++ntri; done
            done
        done
    done

    ntri.println;
}

main;

В основном это порт ответа C, но он быстрее, чем проверенный с clang -O3и icc -O3. Феликс и Ним - это буквально два языка, которые я знаю, которые могут превзойти C и C ++ в тестах. Я работаю над параллельной версией, но это будет немного, пока она не закончится, поэтому я решил опубликовать это заранее.

Я также поставил «неизвестно», потому что мой компьютер не обязательно самый быстрый на земле ...

Команда используется для сборки:

flx --usage=hyperlight -c --static -o sl0 sl0.flx

Сгенерированный C ++ довольно интересен для просмотра:

//Input file: /home/ryan/golf/itri/sl0/sl0.flx
//Generated by Felix Version 15.04.03
//Timestamp: 2015/7/16 20:59:42 UTC
//Timestamp: 2015/7/16 15:59:42 (local)
#define FLX_EXTERN_sl0 FLX_EXPORT
#include "sl0.hpp"
#include <stdio.h>
#define comma ,

//-----------------------------------------
//EMIT USER BODY CODE
using namespace ::flxusr::sl0;

//-----------------------------------------
namespace flxusr { namespace sl0 {

//-----------------------------------------
//DEFINE OFFSET tables for GC
#include "sl0.rtti"
FLX_DEF_THREAD_FRAME
//Thread Frame Constructor
thread_frame_t::thread_frame_t(
) :
  gcp(0),
  shape_list_head(&thread_frame_t_ptr_map)
{}

//-----------------------------------------
//DEFINE FUNCTION CLASS METHODS
#include "sl0.ctors_cpp"
//------------------------------
//C PROC <61624>: _init_
void _init_(FLX_APAR_DECL_ONLY){
  int _i63436_v63436_s;
  int _i63435_v63435_s;
  int s;
  int a;
  int b;
  int c;
  int ntri;
  int n;
      n = static_cast<int>(::std::atoi((::std::string(1<0||1>=PTF argc?"":PTF argv[1])).c_str())); //assign simple
      ntri = 0; //assign simple
      c = 1; //assign simple
    _63421:;
      if(FLX_UNLIKELY((n < c))) goto _63428;
      b = (c + 1 ) / 2 ; //assign simple
    _63422:;
      if(FLX_UNLIKELY((c < b))) goto _63427;
      a = (c - b ) + 1 ; //assign simple
    _63423:;
      if(FLX_UNLIKELY((b < a))) goto _63426;
/*begin match*/
/*match case 1:s*/
      s  = static_cast<int>((::std::sqrt(((static_cast<float>(((2 * (b * b  + (c * c ) )  - (a * a ) ) / 4 ))) + 0.5f ))))/*int.flx: ctor*/; //init
/*begin match*/
/*match case 1:s*/
      _i63435_v63435_s  = static_cast<int>((::std::sqrt(((static_cast<float>(((2 * (a * a  + (c * c ) )  - (b * b ) ) / 4 ))) + 0.5f ))))/*int.flx: ctor*/; //init
/*begin match*/
/*match case 1:s*/
      _i63436_v63436_s  = static_cast<int>((::std::sqrt(((static_cast<float>(((2 * (a * a  + (b * b ) )  - (c * c ) ) / 4 ))) + 0.5f ))))/*int.flx: ctor*/; //init
      if(!((((2 * (b * b  + (c * c ) )  - (a * a ) ) % 4  == 0) && (s * s  == (2 * (b * b  + (c * c ) )  - (a * a ) ) / 4 )  || (((2 * (a * a  + (c * c ) )  - (b * b ) ) % 4  == 0) && (_i63435_v63435_s * _i63435_v63435_s  == (2 * (a * a  + (c * c ) )  - (b * b ) ) / 4 ) ) ) || (((2 * (a * a  + (b * b ) )  - (c * c ) ) % 4  == 0) && (_i63436_v63436_s * _i63436_v63436_s  == (2 * (a * a  + (b * b ) )  - (c * c ) ) / 4 ) ) )) goto _63425;
      {
      int* _tmp63490 = (int*)&ntri;
      ++*_tmp63490;
      }
    _63425:;
      if(FLX_UNLIKELY((a == b))) goto _63426;
      {
      int* _tmp63491 = (int*)&a;
      ++*_tmp63491;
      }
      goto _63423;
    _63426:;
      if(FLX_UNLIKELY((b == c))) goto _63427;
      {
      int* _tmp63492 = (int*)&b;
      ++*_tmp63492;
      }
      goto _63422;
    _63427:;
      if(FLX_UNLIKELY((c == n))) goto _63428;
      {
      int* _tmp63493 = (int*)&c;
      ++*_tmp63493;
      }
      goto _63421;
    _63428:;
      {
      _a12344t_63448 _tmp63494 = ::flx::rtl::strutil::str<int>(ntri) + ::std::string("\n") ;
      ::flx::rtl::ioutil::write(stdout,_tmp63494);
      }
}

//-----------------------------------------
}} // namespace flxusr::sl0
//CREATE STANDARD EXTERNAL INTERFACE
FLX_FRAME_WRAPPERS(::flxusr::sl0,sl0)
FLX_C_START_WRAPPER_PTF(::flxusr::sl0,sl0,_init_)

//-----------------------------------------
//body complete
kirbyfan64sos
источник
2

C # (около 11000?)

using System;
using System.Collections.Generic;

namespace PPCG
{
    class PPCG53100
    {
        static void Main(string[] args)
        {
            int n = int.Parse(args[0]);
            Console.WriteLine(CountOOE(n) + CountEEE(n));
        }

        static int CountOOE(int n)
        {
            // Maps from a^2 + b^2 to (b - a, a + b), which are the exclusive bounds on c.
            IDictionary<int, List<Tuple<int, int>>> pairs = new Dictionary<int, List<Tuple<int, int>>>();

            for (int a = 1; a <= n; a += 2)
            {
                int k = 2 * a * a;
                for (int b = a; b <= n; b += 2, k += 4 * (b - 1))
                {
                    List<Tuple<int, int>> prev;
                    if (!pairs.TryGetValue(k, out prev)) pairs[k] = prev = new List<Tuple<int, int>>();
                    prev.Add(Tuple.Create(b - a, a + b));
                }
            }

            int max = 2 * n * n;
            int count = 0;
            for (int x = 1; x <= n >> 1; x++)
            {
                int k = 4 * x * x;
                for (int y = x; y <= n; y++, k += 4 * y - 2)
                {
                    if (k > max) break;
                    List<Tuple<int, int>> ab;
                    if (pairs.TryGetValue(k, out ab))
                    {
                        foreach (var pair in ab)
                        {
                            // Double-counting isn't possible if a, b are odd.
                            if (pair.Item1 < x << 1 && x << 1 < pair.Item2)
                            {
                                count++;
                            }
                            if (x != y && y << 1 <= n && pair.Item1 < y << 1 && y << 1 < pair.Item2)
                            {
                                count++;
                            }
                        }
                    }
                }
            }

            return count;
        }

        static int CountEEE(int n)
        {
            // Maps from a^2 + b^2 to (b - a, a + b), which are the exclusive bounds on c.
            IDictionary<int, List<Tuple<int, int>>> pairs = new Dictionary<int, List<Tuple<int, int>>>();

            for (int a = 2; a <= n; a += 2)
            {
                int k = 2 * a * a;
                for (int b = a; b <= n; b += 2, k += 4 * (b - 1))
                {
                    List<Tuple<int, int>> prev;
                    if (!pairs.TryGetValue(k, out prev)) pairs[k] = prev = new List<Tuple<int, int>>();
                    prev.Add(Tuple.Create(b - a, a + b));
                }
            }

            // We want to consider m in the range [1, n] and c/2 in the range [1, n/2]
            // But to save dictionary lookups we can scan x in [1, n/2], y in [x, n] and consider both ways round.
            int max = 2 * n * n;
            int count = 0;
            for (int x = 1; x <= n >> 1; x++)
            {
                int k = 4 * x * x;
                for (int y = x; y <= n; y++, k += 4 * y - 2)
                {
                    if (k > max) break;
                    List<Tuple<int, int>> ab;
                    if (pairs.TryGetValue(k, out ab))
                    {
                        foreach (var pair in ab)
                        {
                            // (c1, m1) = (2x, y)
                            // (c2, m2) = (2y, x)

                            int a = (pair.Item2 - pair.Item1) / 2, b = (pair.Item2 + pair.Item1) / 2;
                            int c1 = 2 * x;

                            if (pair.Item1 < c1 && c1 < pair.Item2)
                            {
                                // To deduplicate: the possible sets of integer medians are:
                                //     m_c
                                //     m_a, m_c
                                //     m_b, m_c
                                //     m_a, m_b, m_c
                                // We only want to add if c is (wlog) the shortest edge whose median is integral (or joint integral in case of isosceles triangles).

                                if (c1 <= a) count++;
                                else if (!IsIntegerMedian(b, c1, a))
                                {
                                    if (c1 <= b || !IsIntegerMedian(a, c1, b)) count++;
                                }
                            }

                            int c2 = 2 * y;
                            if (c1 != c2 && c2 <= n && pair.Item1 < c2 && c2 < pair.Item2)
                            {
                                if (c2 <= a) count++;
                                else if (!IsIntegerMedian(b, c2, a))
                                {
                                    if (c2 <= b || !IsIntegerMedian(a, c2, b)) count++;
                                }
                            }
                        }
                    }
                }
            }

            return count;
        }

        private static bool IsIntegerMedian(int a, int b, int c)
        {
            int m2 = 2 * (a * a + b * b) - c * c;
            int s = (int)(0.5f + Math.Sqrt(m2));
            return ((s & 1) == 0) && (m2 == s * s);
        }
    }
}

n принимается в качестве аргумента командной строки.

объяснение

мзнак равно(2a2+2б2-с2)/42a2+2б2знак равно4м2+с2с2ссзнак равно2Сa2+б2знак равно2(м2+С2)a2+б2aб

a2+б2знак равно2(м2+С2)

aб

Питер Тейлор
источник
Я не могу собрать Felix на своей машине, но мое время n=5000составляет 67 секунд для ответа Рето Коради, 48 секунд для ответа Sp3000 и 13 секунд для моего ответа.
Питер Тейлор
0

C, n = 3030 здесь

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define R     return
#define u32 unsigned
#define F        for
#define P     printf

int isq(u32 a)
{u32 y,x,t,i;
 static u32  arr720[]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,180,241,304,369,436,505,649,160,409,496,585,340,544,145,601,244,580,481,640,385,265};
 static char barr[724]={0};
 if(barr[0]==0)F(i=0;i<(sizeof arr720)/sizeof(unsigned);++i)
                if(arr720[i]<720) barr[arr720[i]]=1; 
 if(barr[a%720]==0) R 0;
 y=sqrt(a);
 R y*y==a;
}

int f(u32 a, u32 b, u32 c)
{u32 t,x;
 if(c&1)R 0;
 t= a*a+b*b;
 if(t&1)R 0;
 R isq((2*t-c*c)/4);
}

int h(u32 n)
{u32 cnt,a,c,k,ke,kc,d,v,l,aa,bb,cc;

 cnt=0;
 F(a=1;a<=n;++a)
   {ke=(n-a)/2;
    F(k=0;k<=ke;++k)
        {v=a+k;
         d=v*v+k*k;
         l=sqrt(d);
         v=n/2;
         if(l>v)l=v;
         v=a+k-1;
         if(l>v)l=v;
         F(c=k+1;c<=l;++c)
           {if(isq(d-c*c))
                {bb=a+2*k;cc=2*c;
                 if(bb>cc && f(a, cc,bb)) continue;
                 if( a>cc && f(cc,bb, a)) continue;
                 ++cnt;
                 //P("|a=%u b=%u c=%u", a, bb, cc);
                }
           }
        }
   }
 R cnt; 
}

int main(int c, char** a)
{time_t  ti, tf;
 double   d;
 int     ni;
 u32    n,i;

 if(c!=2||a[1]==0){P("uso: questo_programma.exe  arg1\n ove arg1 e\' un numero positivo\n");R 0;}
 ni=atoi(a[1]);
 if(ni<=0){P("Parametro negativo o zero non permesso\n");R 0;}
 n=ni;
 if(n>0xFFFFF){P("Parametro troppo grande non permesso\n"); R 0;}
 F(i=3;i<33;++i)if(i<10||i>21)P("T(%u)=%u|",i, h(i));
 ti=time(0);
 P("\nT(%u)=%u\n", n, h(n));
 tf=time(0);
 d=difftime(tf,ti);
 P("Tempo trascorso = %.2f sec\n", d); 
 R 1;
}

Результаты:

C:\Users\a\b>prog 3030
T(3)=0|T(4)=0|T(5)=0|T(6)=1|T(7)=1|T(8)=2|T(9)=3|T(22)=34|T(23)=37|T(24)=42|T(25)=
45|T(26)=56|T(27)=59|T(28)=65|T(29)=67|T(30)=74|T(31)=79|T(32)=91|
T(3030)=3321226
Tempo trascorso = 60.00 sec

приведенный выше код будет переводом в C ответа Axiom (если мы не будем считать функцию isq ()).

Мой компилятор не связывает функцию, другие используют sqrtf () ... здесь нет функции sqrt для float ... Они уверены, что sqrtf это стандартная функция C?

RosLuP
источник
(начиная с C99)
Питер Тейлор
0

APL NARS, n = 239 282 за 59 секунд

f←{(a b c)←⍵⋄1=2∣c:0⋄t←+/a b*2⋄1=2∣t:0⋄0=1∣√4÷⍨(2×t)-c*2}

∇r←g n;cnt;c;a;k;kc;ke;d;l;bb;cc
    r←⍬⋄cnt←0
    :for a :in 1..n 
       ke←⌊(n-a)÷2
       :for k :in 0..ke
          d←((a+k)*2)+k*2
          kc←⌊⌊/(n÷2),(a+k-1),√d
          →B×⍳kc<k+1  
          :for c :in (k+1)..kc
            →C×⍳∼1e¯9>1∣√d-c*2
               bb←a+2×k⋄cc←2×c
               →C×⍳(bb>cc)∧f a  cc bb
               →C×⍳( a>cc)∧f cc bb  a
               cnt+←1
               ⍝r←r,⊂a bb cc
   C:     :endfor
   B:  :endfor
    :endfor
    r←r,cnt
∇

(я пишу один аксиомный ответ в APL):

  g 282 
16712 
  v←5 6 10 20 30 41
  v,¨g¨v
5 0  6 1  10 4  20 27  30 74  41 166 
RosLuP
источник
0

Аксиома, n = 269 через 59 с

isq?(x:PI):Boolean==perfectSquare?(x)

f(a:PI,b:PI,c:PI):Boolean==
    c rem 2=1=>false
    t:=a^2+b^2
    t rem 2=1=>false
    x:=(2*t-c^2)quo 4
    isq?(x)

h(n)==
   cnt:=0  -- a:=a   b:=(a+2*k)  c:=
   r:List List INT:=[]
   for a in 1..n repeat
     ke:=(n-a)quo 2
     for k in 0..ke repeat
         d:=(a+k)^2+k^2 -- (a^2+b^2)/2=(a+k)^2+k^2   m^2+c^2=d
         l:=reduce(min,[sqrt(d*1.), n/2.,a+k-1])
         kc:=floor(l)::INT
         for c in k+1..kc repeat
             if isq?(d-c^2) then
                            bb:=a+2*k; cc:=2*c
                            if bb>cc and f(a,cc,bb) then iterate   -- 2<->3
                            if  a>cc and f(cc,bb,a) then iterate   -- 1<->3
                            cnt:=cnt+1
                            --r:=cons([a,a+2*k,2*c],r)
   r:=cons([cnt],r)
   r

Если a, b, cx - длина сторон одного треугольника стороны максимальной длины n ...

Мы бы знали, что m: = sqrt ((2 * (a ^ 2 + b ^ 2) -cx ^ 2) / 4)

(1) m^2=(2*(a^2+b^2)-cx^2)/4

Как сказал Питер Тейлор, 4 | (2 * (a ^ 2 + b ^ 2) -cx ^ 2) и потому что 2 | 2 * (a ^ 2 + b ^ 2), чем 2 | cx ^ 2 => cx = 2 * с. Так с 1 будет

(2) m^2=(a^2+b^2)/2-c^2

a и b должны иметь одинаковую четность, чтобы мы могли написать b как функцию

(3) a:=a   b:=(a+2*k)

чем у нас это

(4)(a^2+b^2)/2=(a^2+(a+2*k)^2)/2=(a+k)^2+k^2

поэтому (1) можно переписать, см. (2) (3) (4) как:

m^2+c^2=(a+k)^2 + k^2=d         a:=a  b:=(a+2*k)  cx:=2*c

где

a in 1..n  
k in 0..(n-a)/2  
c in k+1..min([sqrt(d*1.), n/2.,a+k-1])

Результаты

(16) -> h 269
   (16)  [[14951]]
                                                  Type: List List Integer
        Time: 19.22 (IN) + 36.95 (EV) + 0.05 (OT) + 3.62 (GC) = 59.83 sec
RosLuP
источник
0

VBA 15 000 за десять секунд!

Я ожидал намного меньше после этих других постов. На Intel 7 с 16 ГБ оперативной памяти я получаю 13-15 000 за десять секунд. На Pentium с 4 ГБ ОЗУ я получаю 5-7000 за ДЕСЯТЬ секунд. Код ниже. Вот последний результат на Pentium

abci= 240, 234, 114, 7367, 147
abci= 240, 235, 125, 7368, 145
abci= 240, 236, 164, 7369, 164
abci= 240, 238, 182, 7370, 221
abci= 240, 239, 31, 7371, 121

Он получил треугольник со сторонами 240, 239, 31 и средой 121. Количество носителей составляет 7 371.

Sub tria()
On Error Resume Next
Dim i As Long, a As Integer, b As Integer, c As Integer, ma As Double, mb As Double, mc As Double, ni As Long, mpr As Long
Dim dtime As Date
dtime = Now
Do While Now < DateAdd("s", 10, dtime)  '100 > DateDiff("ms", dtime, Now) '
    a = a + 1
   ' Debug.Assert a < 23
    b = 1: c = 1
    Do
        ma = 0
        If a < b + c And b < a + c And c < a + b Then
            ma = ((2 * b ^ 2 + 2 * c ^ 2 - a ^ 2) / 4) ^ 0.5
            If ma <> 0 Then ni = i + 1 * -1 * (0 = ma - Fix(ma))
                If ni > i Then
                If ma <> mpr Then
                i = ni
                mpr = ma
                    Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i & ", " & ma
                    GoTo NextTri  'TO AVOID DOUBLE COUNTING
                End If
            End If
       'End If

        mb = 0
        'If b < a + c Then
            mb = ((2 * a ^ 2 + 2 * c ^ 2 - b ^ 2) / 4) ^ 0.5
            If mb <> 0 Then ni = i + 1 * -1 * (0 = mb - Fix(mb))
            If ni > i Then
            If mb <> mpr Then
                i = ni
                mpr = mb
                Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i & ", " & mb
                GoTo NextTri  'TO AVOID DOUBLE COUNTING
            End If
            End If
        'End If

        mc = 0
        'IfThen
            mc = ((2 * b ^ 2 + 2 * a ^ 2 - c ^ 2) / 4) ^ 0.5
            If mc <> 0 Then ni = i + 1 * -1 * (0 = mc - Fix(mc))
            If ni > i Then
            If mc <> mpr Then
            i = ni
            mpr = mc
                Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i & ", " & mc
            End If
            End If
        End If
NextTri:
        Do While c <= b
            'c = c + 1
            ma = 0
            If a < b + c And b < a + c And c < a + b Then

                    ma = ((2 * b ^ 2 + 2 * c ^ 2 - a ^ 2) / 4) ^ 0.5
                    If ma <> 0 Then ni = i + 1 * -1 * (0 = ma - Fix(ma))
                            If ni > i Then
                    If ma <> mpr Then
                        mpr = ma
                i = ni
                    End If
                    Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i & ", " & ma
                    GoTo NextTri2  'TO AVOID DOUBLE COUNTING
                End If
            'End If

            mb = 0
            'If b < a + c Then
                mb = ((2 * a ^ 2 + 2 * c ^ 2 - b ^ 2) / 4) ^ 0.5
                If mb <> 0 Then ni = i + 1 * -1 * (0 = mb - Fix(mb))
                        If ni > i Then
                If mb <> mpr Then
                mpr = mb
                i = ni
                    Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i & ", " & mb
                    GoTo NextTri2  'TO AVOID DOUBLE COUNTING
                End If
                End If
            'End If

            mc = 0
            'If c < b + a Then
                    mc = ((2 * b ^ 2 + 2 * a ^ 2 - c ^ 2) / 4) ^ 0.5
                    If mc <> 0 Then ni = i + 1 * -1 * (0 = mc - Fix(mc))
                            If ni > i Then
                    If mc <> mpr Then
                    mpr = mc
                i = ni
                    Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i & ", " & mc
                    End If
                End If
            End If
       ' Debug.Print "abci= " & a & ", " & b & ", " & c & ", " & i
            c = c + 1
        Loop 'While c <= a
NextTri2:
        b = b + 1
        c = 1
    Loop While b <= a
Loop
Debug.Print i

End Sub
Джордж Лет
источник
1
Добро пожаловать в PPCG!
Мартин Эндер