Algorithme O(nlogn) - trouver trois algorithmes uniformément espacés dans la chaîne binaire

Votre problème est appelé à la MOYENNE dans ce document (1999):

un problème est 3sum-hard s'il y a une réduction sub-quadratique du problème 3SUM: étant donné un ensemble A de n entiers, y a-t-il des éléments a,b,c dans un tel que a+b+c = 0? On ne sait pas si la moyenne est 3SUM dur. Cependant, il y a une réduction linéaire simple de temps de moyenne à 3SUM, dont nous omettons la description.

Wikipedia :

quand les entiers sont dans la gamme [-U... u], 3SUM peut être résolu dans le temps O(n + u lg u) en représentant S comme un vecteur bit et en exécutant une convolution en utilisant FFT.

cela suffit pour résoudre votre problème :).

Ce qui est très l'important, c'est que O(n log n) est la complexité en termes de nombre de zéros et de uns, pas le nombre de ceux (qui pourrait être donné comme un tableau, comme [1,5,9,15]). Vérifier si un ensemble a une progression arithmétique, termes de nombre de 1's, est difficile, et selon ce document à partir de 1999 pas plus rapide algorithme que O(n ² ) est connu, et est conjecturé qu'il n'existe pas. tous ceux qui ne prennent pas cela en compte tentent de résoudre un problème ouvert.

autres informations intéressantes, pour la plupart irrevelant:

limite inférieure:

une limite inférieure facile est un ensemble semblable à un Cantor (nombres 1..3^N-1 ne contenant pas 1 dans leur expansion ternaire) - sa densité est de n^(log_3 2) (environ 0,631). Donc vérifier si l'ensemble n'est pas trop grand, puis vérifier toutes les paires n'est pas suffisant pour obtenir O(N log n). Vous devez enquêter sur la séquence plus intelligemment. Une meilleure limite inférieure est citée ici - c'est n ^{1-C/(log(n))^(1/2)} . Cela signifie Cantor set est pas optimal.

limite supérieure - mon ancien algorithme:

il est connu que pour le grand n, un sous-ensemble de {1,2,...,n} ne contenant pas de progression arithmétique a au plus n/(log n)^(1 / 20e). Le papier sur des triples dans la progression arithmétique prouve plus: l'ensemble ne peut pas contenir plus de n * 2 ²⁸ * (log n / log n) ^1/2 elements. Vous pouvez donc vérifier si cette limite est atteinte et si pas, naïvement vérifier paires. C'est l'algorithme O(N ² * log n / log n), plus rapide que O(n ² ). Malheureusement, "Sur les triplets..."est sur Springer-mais la première page est disponible , et L'exposition de Ben Green est disponible ici , page 28, théorème 24.

soit dit en passant, les papiers sont de 1999 - la même année que la première que j'ai mentionnée, donc c'est probablement la raison pour laquelle la première ne mentionne pas ce résultat.

ce n'est pas une solution, mais une ligne de pensée similaire à ce que Olexiy pensait

je jouais avec la création de séquences avec le nombre maximum de uns, et ils sont tous très intéressants, j'ai obtenu jusqu'à 125 chiffres et voici les 3 premiers numéros qu'il a trouvé en essayant d'insérer autant de bits '1' que possible:

• 11011000011011000000000000001101100001101100000000000000000000000000000000000000000110110000110110000000000000011011000011011
• 10110100010110100000000000010110100010110100000000000000000000000000000000000000000101101000101101000000000000101101000101101
• 10011001010011001000000000010011001010011001000000000000000000000000000000000000010011001010011001000000000010011001010011001

notez qu'ils sont tous fractales (pas trop surprenant, étant donné les contraintes). Il peut y avoir quelque chose dans la pensée à l'envers, peut-être que si la chaîne n'est pas une fractale d'avec une caractéristique, alors elle doit avoir un motif répétitif?

merci à beta pour le meilleur terme pour décrire ces nombres.

mise à Jour: Hélas, il semble que le modèle se décompose en commençant par une initiale assez grande chaîne, telle que: 10000000000001:

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001

je soupçonne qu'une approche simple qui ressemble à O(N^2) donnera en fait quelque chose de mieux, comme O(n ln(n)). Les séquences qui prennent le plus de temps à tester (pour tout n) sont ceux qui ne contiennent pas de trios, et qui met de sévères restrictions sur le nombre de 1 dans la séquence.

j'ai trouvé quelques arguments agités à la main, mais je n'ai pas été en mesure de trouver une preuve ordonnée. Je vais tenter ma chance dans le noir: la réponse est une idée très intelligente le professeur le sait depuis si longtemps que ça semble évident, mais c'est beaucoup trop dur pour les étudiants. (Soit ça, soit vous avez dormi pendant la conférence qui l'a couvert.)

révision: 2009-10-17 23: 00

j'ai lancé ceci sur de grands nombres (comme, des chaînes de 20 millions) et je crois maintenant que cet algorithme n'est pas O(logn). Malgré cela, c'est une implémentation assez cool et contient un certain nombre d'optimisations qui le fait fonctionner très rapidement. Il évalue tous les arrangements de chaînes binaires 24 ou moins de chiffres en moins de 25 secondes.

j'ai mis à jour le code pour inclure l'observation 0 <= L < M < U <= X-1 de plus tôt aujourd'hui.

Original

c'est, en principe, similaire à une autre question j'ai répondu . Ce code examinait également trois valeurs d'une série et déterminait si un triplet satisfaisait à une condition. Voici le code C adapté de cela:

using System;
using System.Collections.Generic;

namespace StackOverflow1560523
{
    class Program
    {
        public struct Pair<T>
        {
            public T Low, High;
        }
        static bool FindCandidate(int candidate, 
            List<int> arr, 
            List<int> pool, 
            Pair<int> pair, 
            ref int iterations)
        {
            int lower = pair.Low, upper = pair.High;
            while ((lower >= 0) && (upper < pool.Count))
            {
                int lowRange = candidate - arr[pool[lower]];
                int highRange = arr[pool[upper]] - candidate;
                iterations++;
                if (lowRange < highRange)
                    lower -= 1;
                else if (lowRange > highRange)
                    upper += 1;
                else
                    return true;
            }
            return false;
        }
        static List<int> BuildOnesArray(string s)
        {
            List<int> arr = new List<int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] == '1')
                    arr.Add(i);
            return arr;
        }
        static void BuildIndexes(List<int> arr, 
            ref List<int> even, ref List<int> odd, 
            ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
        {
            for (int i = 0; i < arr.Count; i++)
            {
                bool isEven = (arr[i] & 1) == 0;
                if (isEven)
                {
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
                    even.Add(i);
                }
                else
                {
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
                    odd.Add(i);
                }
            }
        }

        static int FindSpacedOnes(string s)
        {
            // List of indexes of 1s in the string
            List<int> arr = BuildOnesArray(s);
            //if (s.Length < 3)
            //    return 0;

            //  List of indexes to odd indexes in arr
            List<int> odd = new List<int>(), even = new List<int>();

            //  evenIndex has indexes into arr to bracket even numbers
            //  oddIndex has indexes into arr to bracket odd numbers
            List<Pair<int>> evenIndex = new List<Pair<int>>(), 
                oddIndex = new List<Pair<int>>(); 
            BuildIndexes(arr, 
                ref even, ref odd, 
                ref evenIndex, ref oddIndex);

            int iterations = 0;
            for (int i = 1; i < arr.Count-1; i++)
            {
                int target = arr[i];
                bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) || 
                    FindCandidate(target, arr, even, evenIndex[i], ref iterations);
                if (found)
                    return iterations;
            }
            return iterations;
        }
        static IEnumerable<string> PowerSet(int n)
        {
            for (long i = (1L << (n-1)); i < (1L << n); i++)
            {
                yield return Convert.ToString(i, 2).PadLeft(n, '0');
            }
        }
        static void Main(string[] args)
        {
            for (int i = 5; i < 64; i++)
            {
                int c = 0;
                string hardest_string = "";
                foreach (string s in PowerSet(i))
                {
                    int cost = find_spaced_ones(s);
                    if (cost > c)
                    {
                        hardest_string = s;
                        c = cost;
                        Console.Write("{0} {1} {2}\r", i, c, hardest_string);
                    }
                }
                Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
            }
        }
    }
}

les principales différences sont:

1. recherche Exhaustive de solutions
   
   Ce code génère un ensemble de données pour trouver les plus difficiles d'entrée à résoudre pour cet algorithme.
2. Toutes les solutions contre les plus difficiles à résoudre
   
   Le code de la question précédente a généré toutes les solutions en utilisant un générateur python. Ce code affiche juste le plus dur pour chaque longueur de motif.
3. algorithme de notation
   
   Ce code vérifie la distance de l'élément central à sa gauche - et bord de droite. Le code python testait si une somme était supérieure ou inférieure à 0.
4. Convergence sur un candidat
   
   Le code actuel fonctionne du milieu vers le bord pour trouver un candidat. Le code du problème précédent fonctionnait des bords vers le milieu. Ce dernier changement, donne une grande amélioration de la performance.
5. utilisation de pools pairs et impairs
   
   D'après les observations faites à la fin du présent rapport en écriture, le code cherche des paires de nombres pairs de paires de nombres impairs pour trouver L et U, en gardant m fixe. Cela réduit le nombre de recherches par précalcul. Par conséquent, le code utilise deux niveaux d'indirection dans la boucle principale de FindCandidate et nécessite deux appels à FindCandidate pour chaque élément du milieu: une fois pour les nombres pairs et une fois pour les nombres impairs.

l'idée générale est de travailler sur des indices, et non sur la représentation brute des données. Le calcul d'un tableau où l'1 apparaissent permet à l'algorithme à exécuter en temps proportionnel au nombre de 1 dans les données, plutôt que dans le temps proportionnel à la longueur des données. Il s'agit d'une transformation standard: créer une structure de données qui permet des opérations plus rapides tout en gardant l'équivalent du problème.

les résultats sont périmés: supprimé.

Edit: 2009-10-16 18: 48

sur les données de yx, qui est donné une certaine crédibilité dans les autres réponses comme représentant des données dures pour calculer, je reçois ces résultats... J'ai enlevé ces. Ils ne sont pas à jour.

je voudrais souligner que ces données ne sont pas les plus difficiles pour mon algorithme, donc je pense que l'hypothèse que les fractales de yx sont les plus difficiles à résoudre est erronée. Le pire cas pour un algorithme particulier, je m'attends, dépendra de l'algorithme lui-même et ne sera probablement pas cohérente entre les différents algorithmes.

Edit: 2009-10-17 13: 30

autres observations à ce sujet.

convertissez D'abord la chaîne de 0 et de 1 en un tableau d'indices pour chaque position du 1. Disons que la longueur de ce tableau A est X. Alors le but est de trouver

0 <= L < M < U <= X-1

tel que

A[M] - A[L] = A[U] - A[M]

ou

2*A[M] = A[L] + A[U]

puisque A[L] et a [U] somme à un pair nombre, ils ne peuvent pas l'être (pair, impair) ou (bizarre, même). La recherche d'une correspondance pourrait être améliorée en divisant un[] en bassins impairs et pairs et en cherchant des correspondances sur un[M] dans les bassins de candidats impairs et pairs à tour de rôle.

cependant, c'est plus une optimisation des performances qu'une amélioration algorithmique, je pense. Le nombre de comparaisons devrait diminuer, mais l'ordre de l'algorithme devrait être le même.

Modifier 2009-10-18 00: 45

encore une autre optimisation se produit à moi, dans la même veine que la séparation des candidats en Pair et Impair. Puisque les trois indices doivent s'ajouter à un multiple de 3( a, A+x, a+2x -- mod 3 est 0, indépendamment de A et x), vous pouvez séparer L, M, et U dans leurs valeurs mod 3:

M  L  U
0  0  0
   1  2
   2  1
1  0  2
   1  1
   2  0
2  0  1
   1  0
   2  2

en fait, vous pouvez combiner cela avec l'observation pair / impair et les séparer dans leurs valeurs mod 6:

M  L  U
0  0  0
   1  5
   2  4
   3  3
   4  2
   5  1

et ainsi de suite. Cela permettrait une optimisation supplémentaire des performances, mais pas une accélération algorithmique.

N'a pas encore trouvé la solution :(, mais avoir quelques idées.

Que faire si nous partons d'un problème inverse: construire une séquence avec le nombre maximum de 1s et sans trios uniformément espacés. Si vous pouvez prouver que le nombre maximum de 1s est o(n), alors vous pouvez améliorer votre estimation en itérant seulement par la liste de 1s seulement.

cela peut aider....

ce problème se réduit à ce qui suit:

étant donné une séquence d'entiers positifs, trouver une suite contiguë divisée en un préfixe et un suffixe tel que la somme du préfixe de la suite est égale à la somme du suffixe de la suite.

par exemple, étant donné une séquence de [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ] , nous trouverions une suite de [ 3, 6, 5, 2, 2] avec un préfixe [ 3, 6 ] avec un préfixe 9 et un suffixe [ 5, 2, 2 ] avec un suffixe 9 .

la réduction est la suivante:

avec une séquence de zéros et de uns, et en commençant par le plus à gauche, continuez à vous déplacer vers la droite. Chaque fois qu'un autre est rencontré, inscrire le nombre de mouvements depuis que le précédent a été rencontré et ajouter ce nombre à la séquence résultante.

par exemple , étant donné une séquence de [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ] , nous trouverions la réduction de [ 1, 3, 4] . De cette réduction, nous calculons la zone sous-suite de [ 1, 3, 4] , le préfixe [ 1, 3] avec la somme de 4 , et le suffixe de [ 4 ] avec la somme de 4 .

cette réduction peut être calculée en O(n) .

malheureusement, je ne sais pas où aller à partir d'ici.

pour le type de problème simple (c.-à-d. Vous cherchez trois" 1 " avec seulement (c.-à-d. zéro ou plus)" 0 " entre elle), son tout simple: vous pourriez juste diviser la séquence à chaque" 1 " et chercher deux postérieures adjacentes ayant la même longueur (la seconde postérité n'étant pas la dernière, bien sûr). Évidemment, cela peut être fait dans O(n) time.

Pour la version plus complexe (c'est à dire vous recherchez un index je et un gap g >0 tel que s[i]==s[i+g]==s[i+2*g]=="1" ), Je ne suis pas sûr, s'il existe un O(N log n) solution, car il ya peut-être O(n2) triplets ayant cette propriété (pensez à une chaîne de tous ceux, Il ya environ n2/2 tels triplés). Bien sûr, vous n'en cherchez qu'un, mais je ne sais pas comment le trouver ...

une question amusante, mais une fois que vous réalisez que le modèle réel entre deux ' 1 'n'a pas d'importance, l'algorithme devient:

• analyse de regarder pour un '1'
• à partir de la position suivante scan pour un autre '1' (à la fin du tableau moins la distance du premier '1' actuel ou bien le 3ème '1' serait hors limites)
• si à la position du 2e '1' plus la distance au premier 1' un troisième '1' est trouvé, nous ont uniformément des espaces.

en code, JTest fashion, (notez que ce code n'est pas écrit pour être le plus efficace et j'ai ajouté quelques println's pour voir ce qui se passe.)

import java.util.Random;

import junit.framework.TestCase;

public class AlgorithmTest extends TestCase {

 /**
  * Constructor for GetNumberTest.
  *
  * @param name The test's name.
  */
 public AlgorithmTest(String name) {
  super(name);
 }

 /**
  * @see TestCase#setUp()
  */
 protected void setUp() throws Exception {
  super.setUp();
 }

 /**
  * @see TestCase#tearDown()
  */
 protected void tearDown() throws Exception {
  super.tearDown();
 }

 /**
  * Tests the algorithm.
  */
 public void testEvenlySpacedOnes() {

  assertFalse(isEvenlySpaced(1));
  assertFalse(isEvenlySpaced(0x058003));
  assertTrue(isEvenlySpaced(0x07001));
  assertTrue(isEvenlySpaced(0x01007));
  assertTrue(isEvenlySpaced(0x101010));

  // some fun tests
  Random random = new Random();

  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
 }

 /**
  * @param testBits
  */
 private boolean isEvenlySpaced(long testBits) {
  String testString = Long.toBinaryString(testBits);
  char[] ones = testString.toCharArray();
  final char ONE = '1';

  for (int n = 0; n < ones.length - 1; n++) {

   if (ONE == ones[n]) {
    for (int m = n + 1; m < ones.length - m + n; m++) {

     if (ONE == ones[m] && ONE == ones[m + m - n]) {
      System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
      System.out.println("               at: " + n + ", " + m + ", " + (m + m - n));
      return true;
     }
    }
   }
  }

  System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
  return false;
 }
}

j'ai pensé à une approche "diviser pour mieux régner" qui pourrait fonctionner.

tout d'abord, dans le prétraitement, vous devez insérer tous les numéros inférieurs à la moitié de votre taille d'entrée ( n /3) dans une liste.

avec une chaîne de caractères: 0000010101000100 (notez que cet exemple est valide)

insérer tous les nombres premiers (et 1) de 1 à (16/2) dans une liste: {1, 2, 3, 4, 5, 6, 7}

alors divisez-le en moitié:

100000101 01000100

continuez jusqu'à ce que vous arriviez à des cordes de taille 1. Pour toutes les chaînes de taille 1 avec un 1 en elles, ajoutez l'index de la chaîne à la liste des possibilités; sinon, retournez -1 pour échec.

vous devrez également retourner une liste des distances encore possibles, associées à chaque index de départ. (Commencez par la liste ci-dessus et supprimer des numéros que vous allez) Ici, une liste vide signifie vous n'avez affaire qu'à un 1 et donc n'importe quel espacement est possible à ce point; sinon la liste inclut des écartements qui doivent être écartés.

reprenant ainsi l'exemple ci-dessus:

1000 0101 0100 0100

10 00 01 01 01 00 01 00

1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0

dans la première étape de combinaison, nous avons huit séries de deux maintenant. Dans le premier, nous avons la possibilité d'un ensemble, mais nous apprenons que l'espacement par 1 est impossible à cause de l'autre zéro. Donc nous retournons 0 (pour l'indice) et {2,3,4,5,7} pour le fait que l'espacement par 1 est impossible. Dans la deuxième, nous n'avons rien et donc retourner -1. Dans la troisième on a un match sans écartement éliminé dans l'index 5, donc retour 5, {1,2,3,4,5,7}. Dans la quatrième paire, nous retournons 7, {1,2,3,4,5,7}. Dans le cinquième, retour 9, {1,2,3,4,5,7}. Dans la sixième, retour -1. Dans le septième, retour 13, {1,2,3,4,5,7}. Dans la huitième, retour -1.

se combinant à nouveau en quatre séries de quatre, nous avons:

1000 : Retour (0, {4,5,6,7}) 0101 : Retour (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7}) 0100 : retour (9, {3,4,5,6,7}) 0100 : Retour (13, {3,4,5,6,7})

se combinant en ensembles de huit:

10000101 : Retour (0, {5,7}), (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7}) 01000100 : retour (9, {4,7}), (13, {3,4,5,6,7})

se combinant en un ensemble de seize:

10000101 01000100

comme nous avons progressé, nous continuons à vérifier toutes les possibilités jusqu'à présent. Jusqu'à cette étape nous avons laissé des choses qui sont allées au-delà de la fin de la chaîne, mais maintenant nous pouvons vérifier toutes les possibilités.

en gros, nous vérifions le premier 1 avec des intervalles de 5 et 7, et nous constatons qu'ils ne s'alignent pas à 1. (Notez que chaque contrôle est CONSTANT, pas le temps linéaire) alors nous vérifier la deuxième (index 5) avec des espacements de 2, 3, 4, 5, 6, et 7-- ou nous le ferions, mais nous pouvons nous arrêter à 2 puisque cela correspond en fait.

Phew! C'est un algorithme assez long.

je ne sais pas à 100% si c'est O(n log n) en raison de la dernière étape, mais tout jusqu'à il y a certainement O(n log n) aussi loin que je peux dire. J'y reviendrai plus tard et j'essaierai d'affiner la dernière étape.

EDIT: Changé ma réponse à réfléchir Welbog commentaire. Désolé pour l'erreur. J'écrirai quelques pseudo plus tard, aussi, quand j'aurai un peu plus de temps pour déchiffrer ce que j'ai écrit à nouveau. ;- )

je vais donner mon avis approximatif ici, et que ceux qui sont mieux avec le calcul de la complexité pour m'aider sur la façon dont mon algorithme se déplace en O-notation Sage

1. chaîne binaire fournie 0000010101000100 (à titre d'exemple)
2. tête de culture et queue de zéros - > 00000 101010001 00
3. nous avons 101010001 de calcul précédent
4. vérifier si le bit du milieu est "un", si vrai, trouvé valide trois uniformément espacés 'uns' (seulement si le nombre de bits est impair numéroté)
5. corrélativement, si le nombre de bits recadrés est pair numéroté, la tête et la queue "un" ne peuvent pas faire partie de "Un" également espacés,
6. nous utilisons 1010100001 comme exemple (avec un "zéro" supplémentaire pour devenir une récolte numérotée pair), dans ce cas, nous devons recadrer, puis devient - > 10101 00001
7. nous obtenons 10101 à partir de calculs précédents, et vérifier la mi-bit, et nous avons trouvé le même

Je n'ai aucune idée de comment calculer la complexité pour cela, quelqu'un peut-il aider?

edit: ajouter du code pour illustrer mon idée

edit2: j'ai essayé de compiler mon code et j'ai trouvé quelques erreurs majeures, corrigé

char *binaryStr = "0000010101000100";

int main() {
   int head, tail, pos;
   head = 0;
   tail = strlen(binaryStr)-1;
   if( (pos = find3even(head, tail)) >=0 )
      printf("found it at position %d\n", pos);
   return 0;
}

int find3even(int head, int tail) {
   int pos = 0;
   if(head >= tail) return -1;
   while(binaryStr[head] == '0') 
      if(head<tail) head++;
   while(binaryStr[tail] == '0') 
      if(head<tail) tail--;
   if(head >= tail) return -1;
   if( (tail-head)%2 == 0 && //true if odd numbered
       (binaryStr[head + (tail-head)/2] == '1') ) { 
         return head;
   }else {
      if( (pos = find3even(head, tail-1)) >=0 )
         return pos;
      if( (pos = find3even(head+1, tail)) >=0 )
         return pos;
   }
   return -1;
}

j'ai trouvé quelque chose comme ça:

def IsSymetric(number):
    number = number.strip('0')

    if len(number) < 3:
        return False
    if len(number) % 2 == 0:
        return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
    else:
        if number[len(number)//2] == '1':
            return True
        return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
    return False

c'est inspiré par andycjw.

1. tronquer les zéros.
2. Si, même alors, l'essai de deux sous-chaîne 0 - (len-2) (passez dernier caractère) et de 1 - (len-1) (passez le premier char)
3. si ce n'est même si l'omble du milieu est un que nous avons le succès. Sinon, divisez la corde dans le midle sans l'élément midle et vérifiez les deux parties.

quant à la complexité cela pourrait être o(nlogn) comme dans chaque récursion nous nous divisons par deux.

J'espère que ça aidera.

Ok, je vais essayer de résoudre le problème. Je pense que je peux prouver un algorithme O(N log (n)) Qui est similaire à ceux déjà discutés en utilisant un arbre binaire équilibré pour stocker les distances entre 1. Cette approche a été inspirée par L'observation du Ministère de la justice visant à réduire le problème à une liste de distances entre les 1.

pourrions-nous scanner la chaîne de saisie pour construire un arbre binaire équilibré autour de la position de 1's de sorte que chaque noeud stocke la position du 1 et chaque bord est marqué avec la distance au 1 adjacent pour chaque noeud d'enfant. Par exemple:

10010001 gives the following tree

      3
     / \
  2 /   \ 3
   /     \
  0       7

cela peut être fait en O(N log(n)) puisque, pour une chaîne de taille n, chaque insertion prend O(log(n)) dans le pire des cas.

alors le problème est de chercher dans l'arbre pour découvrir si, à n'importe quel noeud, il y a un chemin à partir de ce noeud à travers l'enfant de gauche qui a la même distance qu'un chemin à travers l'enfant de droite. Cela peut être fait récursivement sur chaque sous-arbre. Lors de la fusion de deux sous-arbres dans la recherche, nous devons comparer les distances des chemins dans le sous-arbre de gauche avec les distances des chemins dans le droit. Puisque le nombre de chemins dans un sous-arbre sera proportionnel à log(n), et que le nombre de noeuds est n, je crois que cela peut être fait en temps O(N log(n)).

ai-je manqué quelque chose?

cela semblait être un problème amusant, alors j'ai décidé d'essayer.

je fais l'hypothèse que 111000001 trouverait les 3 premiers et réussirait. Essentiellement le nombre de zéros suivant le 1 est la chose importante, puisque 0111000 est le même que 111000 selon votre définition. Une fois que vous avez trouvé deux cas de 1, le premier trouvé complète la trilogie.

Voici en Python:

def find_three(bstring):
    print bstring
    dict = {}
    lastone = -1
    zerocount = 0
    for i in range(len(bstring)):
        if bstring[i] == '1':
            print i, ': 1'
            if lastone != -1:
                if(zerocount in dict):
                    dict[zerocount].append(lastone)
                    if len(dict[zerocount]) == 2:
                        dict[zerocount].append(i)
                        return True, dict
                else:
                    dict[zerocount] = [lastone]
            lastone = i
            zerocount = 0
        else:
            zerocount = zerocount + 1
    #this is really just book keeping, as we have failed at this point
    if lastone != -1:
        if(zerocount in dict):
            dict[zerocount].append(lastone)
        else:
            dict[zerocount] = [lastone]
    return False, dict

C'est un premier essai, je suis sûr que cela pourrait être écrit dans un nettoyant. Veuillez énumérer les cas où cette méthode échoue ci-dessous.

je suppose que la raison pour laquelle il s'agit de nlog (n) est due à ce qui suit:

• pour trouver le 1 qui est le début du triplet, vous devez vérifier les caractères (n-2). Si vous ne l'avez pas trouvé à ce point, vous ne pourrez pas (chars n-1 et n ne peuvent pas démarrer un triplet) (O (n))
• pour trouver le second 1 qui est la partie du triplet (commencée par le premier), vous devez vérifier m / 2 (m=n-x, où x est l'offset du premier 1) caractère. C'est parce que, si vous n'avez pas trouvé le second 1 au moment où vous êtes à mi-chemin entre le premier et la fin, vous ne le trouverez pas... puisque le troisième 1 doit être exactement la même distance après le deuxième. (o (log (n)))
• Il O(1) pour trouver le dernier 1 puisque vous savez que l'indice qu'il doit être au par le temps, vous trouvez la première et la deuxième.

ainsi, vous avez n, log(n), et 1... O (nlogn)

Edit: Oups, my bad. Mon cerveau avait réglé que n / 2 était logn... ce qui n'est évidemment pas le cas (doubler le nombre d'items Double encore le nombre d'itérations sur la boucle interne). C'est toujours à n^2, Ne pas résoudre le problème. Eh bien, au moins j'ai pu écrire un code:)

mise en Œuvre dans Tcl

proc get-triplet {input} {
    for {set first 0} {$first < [string length $input]-2} {incr first} {
        if {[string index $input $first] != 1} {
            continue
        }
        set start [expr {$first + 1}]
        set end [expr {1+ $first + (([string length $input] - $first) /2)}]
        for {set second $start} {$second < $end} {incr second} {
            if {[string index $input $second] != 1} {
                continue
            }
            set last [expr {($second - $first) + $second}]
            if {[string index $input $last] == 1} {
                return [list $first $second $last]
            }
        }
    }
    return {}
}

get-triplet 10101      ;# 0 2 4
get-triplet 10111      ;# 0 2 4
get-triplet 11100000   ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7

je pense avoir trouvé un moyen de résoudre le problème, mais je ne peux pas construire une preuve formelle. La solution que j'ai faite est écrite en Java, et elle utilise un compteur 'n' pour compter le nombre d'accès list/array qu'elle fait. Donc n doit être inférieur ou égal à stringLength*log(stringLength) si elle est correcte. J'ai essayé pour les nombres 0 à 2^22, et ça marche.

il commence par itérer sur la chaîne de saisie et faire une liste de tous les index qui en contiennent un. C'est juste O (n).

puis, à partir de la liste des index, elle choisit un premier index, et un secondIndex qui est plus grand que le premier. Ces deux indices doivent tenir, car ils sont dans la liste des index. A partir de là, le troisième indice peut être calculé. Si la chaîne de saisie [thirdIndex] est un 1 alors elle s'arrête.

public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;

//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
    if(input.charAt(i)=='1'){
        ones.add(i);
    }
}

//If less than three ones in list, just stop
if(ones.size()<3){
    return n;
}

int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
    n++;
    firstIndex = ones.get(x);

    for(int y=x+1; y<ones.size()-1; y++){
        n++;
        secondIndex = ones.get(y);
        thirdIndex = secondIndex*2 - firstIndex;

        if(thirdIndex >= input.length()){
            break;
        }

        n++;
        if(input.charAt(thirdIndex) == '1'){
            //This case is satisfied if it has found three evenly spaced ones
            //System.out.println("This one => " + input);
            return n;
        }
    }
}

return n;

}

note supplémentaire: le compteur n n'est pas incrémenté lorsqu'il itère sur la chaîne de saisie pour construire la liste des index. Cette opération est O (n), donc elle n'aura pas d'effet sur la complexité de l'algorithme de toute façon.

l'un des aspects du problème est de penser aux facteurs et aux changements.

avec shifting, vous comparez la chaîne de uns et de zéros avec une version décalée de lui-même. Vous prenez ensuite ceux qui correspondent. Prenez cet exemple décalé de deux:

1010101010
  1010101010
------------
001010101000

les 1 résultants (bitwise ANDed), doivent représenter tous les 1 qui sont également espacés par deux. Le même exemple décalé de trois:

1010101010
   1010101010
-------------
0000000000000

Dans ce cas là il y a des N ° 1 qui sont espacés de trois.

alors qu'est-ce que ça te dit? Il suffit de tester les équipes qui sont des nombres premiers. Par exemple, dites que vous avez deux 1 qui sont à six. Vous n'auriez qu'à tester "deux" équipes et "trois" équipes (puisque celles-ci divisent six). Par exemple:

10000010 
  10000010 (Shift by two)
    10000010
      10000010 (We have a match)

10000010
   10000010 (Shift by three)
      10000010 (We have a match)

donc les seuls postes que vous devez vérifier sont 2,3,5,7,11,13 etc. Jusqu'au premier la plus proche de la racine carrée de la taille de la chaîne de chiffre.

presque résolu?

je pense que je suis plus proche d'une solution. En gros:

1. scannez la chaîne pour les 1. Pour chaque 1 note c'est le reste après avoir pris un module de sa position. Le module varie de 1 à la moitié de la taille de la chaîne. C'est parce que la plus grande taille de séparation possible est la moitié de la corde. Cela se fait en O(n^2). MAIS. Seuls les modules prime doivent être vérifiés O(N^2/log (n))
2. trier la liste des modules/restes dans l'ordre le plus grand module d'abord, cela peut être fait en O(N*log(n)) temps.
3. rechercher trois modules/restes consécutifs qui sont les mêmes.
4. d'une façon ou d'une autre, récupérez la position des uns!

je pense que le plus grand indice de la réponse, est que les algorithmes de tri les plus rapides, sont O(N*log(n)).

WRONG

Étape 1 est faux, comme l'a fait remarquer un collègue. Si on a 1 à la position 2, 12 et 102. En prenant un module de 10, ils auraient tous les mêmes restes, et pourtant ils ne sont pas également espacés! Désolé.

Voici quelques réflexions qui, malgré tous mes efforts, ne semblent pas à s'envelopper dans un arc. Encore, ils pourraient être un point de départ utile pour quelqu'un d'analyse.

envisager la solution proposée comme suit, qui est l'approche que plusieurs gens ont suggéré, y compris moi-même dans une version antérieure de cette réponse. :)

1. zéros D'orientation et de queue.
2. scanner la chaîne je cherche les 1.
3. quand un 1 est trouvé:
   1. Supposons que c'est le milieu 1 de la solution.
   2. pour chaque priorité 1, Utilisez sa position sauvegardée pour calculer la position prévue de la finale 1.
   3. si la position calculée est après la fin de la chaîne de caractères, elle ne peut pas faire partie de la solution, alors supprimez la position de la liste des candidats.
   4. Vérifiez la solution.
4. si la solution n'a pas été trouvée, ajouter le 1 actuel à la liste des candidats.
5. répéter jusqu'à ce qu'il n'y ait plus de 1.

considérez maintenant les chaînes d'entrée comme les suivantes, qui n'auront pas de solution:

101
101001
1010010001
101001000100001
101001000100001000001

en général, il s'agit de la concaténation des chaînes k de la forme j 0 suivie d'un 1 pour j de zéro à k-1.

k=2  101
k=3  101001
k=4  1010010001
k=5  101001000100001
k=6  101001000100001000001

noter que les longueurs des substrats sont 1, 2, 3, etc. Ainsi, la taille du problème n a des substrats de longueurs de 1 à k tels que n = k(k+1)/2.

k=2  n= 3  101
k=3  n= 6  101001
k=4  n=10  1010010001
k=5  n=15  101001000100001
k=6  n=21  101001000100001000001

notez que k suit également le nombre de 1 que nous devons considérer. Rappelez-vous que chaque fois que nous voyons un 1, nous devons considérer tous les 1 vu jusqu'à présent. Alors, quand nous voyons la seconde 1, nous ne considérerons que le premier, quand nous voyons le troisième 1, de revenir sur les deux premiers, quand on voit le quatrième 1, nous avons besoin de reconsidérer les trois premiers, et ainsi de suite. À la fin de l'algorithme, nous avons considéré k(k-1)/2 paires de 1. Appelle ça p.

k=2  n= 3  p= 1  101
k=3  n= 6  p= 3  101001
k=4  n=10  p= 6  1010010001
k=5  n=15  p=10  101001000100001
k=6  n=21  p=15  101001000100001000001

la relation entre n et p est que n = p + K.

le processus de passer à travers la chaîne prend du temps. Chaque fois qu'on rencontre un 1, on effectue un maximum de comparaisons (k-1). Puisque n = k(k+1)/2, n > k**2, sqrt(n) > k. Cela nous donne O(n sqrt(n)) ou O(n**3/2). Notez cependant peut-être pas une vraiment serré limite, parce que le nombre de comparaisons va de 1 à un maximum de k, il n'est pas k tout le temps. Mais je ne sais pas comment expliquer ça dans les maths.

Il n'est toujours pas en O(n log(n)). En outre, Je ne peux pas prouver que ces entrées sont les pires cas, bien que je pense qu'ils le sont. Je pense qu'un emballage plus dense de 1 à l'avant résulte en un emballage encore plus clairsemé à la fin.

puisque quelqu'un peut encore le trouver utile, voici mon code pour cette solution en Perl:

#!/usr/bin/perl

# read input as first argument
my $s = $ARGV[0];

# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";

# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;

# prime the position list with the first '1' at position 0
my @p = (0);

# start at position 1, which is the second character
my $i = 1;

print "the string is $s\n\n";

while ($i < length($s)) {
   if (substr($s, $i, 1) eq '1') {
      print "found '1' at position $i\n";
      my @t = ();
      # assuming this is the middle '1', go through the positions
      # of all the prior '1's and check whether there's another '1'
      # in the correct position after this '1' to make a solution
      while (scalar @p) {
         # $p is the position of the prior '1'
         my $p = shift @p;
         # $j is the corresponding position for the following '1'
         my $j = 2 * $i - $p;
         # if $j is off the end of the string then we don't need to
         # check $p anymore
         next if ($j >= length($s));
         print "checking positions $p, $i, $j\n";
         if (substr($s, $j, 1) eq '1') {
            print "\nsolution found at positions $p, $i, $j\n";
            exit 0;
         }
         # if $j isn't off the end of the string, keep $p for next time
         push @t, $p;
      }
      @p = @t;
      # add this '1' to the list of '1' positions
      push @p, $i;
   }
   $i++;
}

print "\nno solution found\n";

en scannant 1s, ajoutez leurs positions à une liste. Lors de l'ajout de la seconde et des suivantes 1s, comparez-les à chaque position dans la liste jusqu'à présent. L'espacement est égal à currentOne (centre) - previousOne (gauche). Le bit de droite est currentOne + spacing. Si c'est 1, la fin.

la liste de ceux croît inversement avec l'espace entre eux. En termes simples, si vous avez beaucoup de 0 entre les 1 (comme dans le pire des cas), votre liste de 1 connus croîtra très lentement.

using System;
using System.Collections.Generic;

namespace spacedOnes
{
    class Program
    {
        static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};

        static void Main(string[] args)
        {
            var bytes = new byte[4];
            var r = new Random();
            r.NextBytes(bytes);
            foreach (var b in bytes) {
                Console.Write(getByteString(b));
            }
            Console.WriteLine();
            var bitCount = bytes.Length * 8;
            var done = false;
            var onePositions = new List<int>();
            for (var i = 0; i < bitCount; i++)
            {
                if (isOne(bytes, i)) {
                    if (onePositions.Count > 0) {
                        foreach (var knownOne in onePositions) {
                            var spacing = i - knownOne;
                            var k = i + spacing;
                            if (k < bitCount && isOne(bytes, k)) {
                                Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
                                done = true;
                                break;
                            }
                        }
                    }
                    if (done) {
                        break;
                    }
                    onePositions.Add(i);
                }
            }
            Console.ReadKey();
        }

        static String getByteString(byte b) {
            var s = new char[8];
            for (var i=0; i<s.Length; i++) {
                s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
            }
            return new String(s);
        }

        static bool isOne(byte[] bytes, int i)
        {
            var byteIndex = i / 8;
            var bitIndex = i % 8;
            return (bytes[byteIndex] & _bits[bitIndex]) > 0;
        }
    }
}

j'ai pensé ajouter un commentaire avant de poster la 22ème solution naïve au problème. Pour les naïfs solution, nous n'avons pas besoin de montrer que le nombre de 1 dans la chaîne est au plus O(log(n)), mais plutôt qu'il est au plus O(sqrt(n*log(n)).

solveur:

def solve(Str):
    indexes=[]
    #O(n) setup
    for i in range(len(Str)):
        if Str[i]=='1':
            indexes.append(i)

    #O((number of 1's)^2) processing
    for i in range(len(indexes)):
        for j in range(i+1, len(indexes)):
                            indexDiff = indexes[j] - indexes[i]
            k=indexes[j] + indexDiff
            if k<len(Str) and Str[k]=='1':
                return True
    return False

c'est essentiellement un peu similaire à l'idée de flybywire et la mise en œuvre, mais en regardant l'avenir au lieu de revenir.

Gourmand Générateur De Chaîne:

#assumes final char hasn't been added, and would be a 1 
def lastCharMakesSolvable(Str):
    endIndex=len(Str)
    j=endIndex-1
    while j-(endIndex-j) >= 0:
        k=j-(endIndex-j)
        if k >= 0 and Str[k]=='1' and Str[j]=='1':
            return True
        j=j-1
    return False



def expandString(StartString=''):
    if lastCharMakesSolvable(StartString):
        return StartString + '0'
    return StartString + '1'

n=1
BaseStr=""
lastCount=0
while n<1000000:
    BaseStr=expandString(BaseStr)
    count=BaseStr.count('1')
    if count != lastCount:
        print(len(BaseStr), count)
    lastCount=count
    n=n+1

(pour ma défense, je suis toujours dans le "apprendre le python" stade de la compréhension)

aussi, sortie potentiellement utile de la construction gourmande de cordes, il y a un saut assez consistant après avoir frappé une puissance de 2 dans le nombre de 1... que je n'étais pas prêt à attendre pour voir frapper 2096.

strlength   # of 1's
    1    1
    2    2
    4    3
    5    4
   10    5
   14    8
   28    9
   41    16
   82    17
  122    32
  244    33
  365    64
  730    65
 1094    128
 2188    129
 3281    256
 6562    257
 9842    512
19684    513
29525    1024

je vais essayer de présenter une approche mathématique. C'est plus un début qu'une fin, donc toute aide, tout commentaire, ou même toute contradiction, sera profondément apprécié. Cependant, si cette approche est prouvé - l'algorithme est une simple recherche dans la chaîne.

1. étant donné un nombre fixe d'espaces k et une chaîne de caractères S , la recherche d'un triplet en K prend O(n) -nous testons simplement pour chaque 0<=i<=(n-2k) si S[i]==S[i+k]==S[i+2k] . Le test prend O(1) et nous le faisons n-k fois où k est une constante, donc il faut O(n-k)=O(n) .

2. supposons qu'il y ait une Proportion Inverse entre le nombre de 1 's et les espaces maximums que nous devons chercher. C'est-à-dire, S'il y a beaucoup de 1 's, il doit y avoir un triplet Et il doit être assez dense; S'il n'y a que peu de 1 's, Le triplet (s'il y en a) peut être assez clairsemé. En d'autres termes, je peux prouver que, si j'ai assez de 1 , tel triplet doit exister - et le plus 1 j'ai, de plus en plus dense triplet doit être trouvé. Cela peut s'expliquer par le Pigeonhole Principe - L'espoir d'élaborer sur ce plus tard.

3. Dire avoir une limite supérieure k sur le nombre possible de places je dois regarder pour. Maintenant, pour chaque 1 situé dans S[i] nous devons Vérifiez 1 dans S[i-1] et S[i+1] , S[i-2] et S[i+2] ,... S[i-k] et S[i+k] . Cela prend O((k^2-k)/2)=O(k^2) pour chaque 1 dans S - en raison de série de Gauss formule de sommation . Notez que ceci diffère de la section 1-j'ai k comme limite supérieure pour le nombre d'Espaces, pas comme un espace constant.

Nous devons prouver O(n*log(n)) . C'est-à-dire que nous devons montrer que k*(number of 1's) est proportionnel à log(n) .

si nous pouvons faire cela, l'algorithme est trivial - pour chaque 1 dans S dont l'index est i , il suffit de chercher 1 de chaque côté jusqu'à la distance k . Si deux personnes ont été trouvées à la même distance, retournez i et k . Encore une fois, la partie délicate serait de trouver k et la preuve de l'exactitude.

I voudrais vraiment apprécier vos commentaires ici - j'ai essayé de trouver la relation entre k et le nombre de 1 sur mon tableau blanc, sans succès jusqu'à présent.

hypothèse:

tout Simplement faux, parler de log(n) numéro de la limite supérieure de la

EDIT:

maintenant j'ai trouvé qu'en utilisant les nombres de Cantor (si correct), la densité sur le jeu est(2/3)^Log_3 (n) (Quelle fonction étrange) et je suis d'accord, log (n)/n La densité est trop forte.

si c'est la limite supérieure, Il y a algorithhitm qui résout ce problème dans au moins O(N*(3/2)^(log(n)/log (3)) temps complexité et O((3/2)^(log(n)/log(3)) complexité de l'espace. (cocher la réponse de la Justice pour algorhitm)

C'est encore beaucoup mieux que O(N^2)

Cette fonction ((3/2)^(log(n)/log(3))) ressemble vraiment à n*log(n) à première vue.

Comment ai-je eu cette formule?

Applaying Chantres numéro de chaîne.

Supposons que la longueur de la chaîne soit 3^p = = n

À chaque étape dans la génération de chaîne de Cantor vous gardez 2/3 du nombre prevous de ceux. Appliquez ce p times.

qui signifie (n * ((2/3)^p)) - > (((3^p)) * ((2/3)^p)) les autres et après simplification 2^p. Cela signifie 2^P ceux dans 3^P string - > (3/2)^P ceux . Remplacer p=log (n) / log(3) et obtenir

((3/2)^(log(n)/log (3))

Que Diriez-vous d'une solution O(n) simple, avec de L'espace O(N^2)? (Utilise l'hypothèse que tous les opérateurs bitwise travaillent dans O (1).)

l'algorithme fonctionne essentiellement en quatre étapes:

Étape 1: pour chaque bit dans votre numéro d'origine, découvrez à quelle distance ceux-ci sont, mais ne considérez qu'une seule direction. (J'ai considéré tous les bits dans la direction du bit le moins significatif.)

Étape 2: Inverser l'ordre des bits dans le d'entrée;

Étape 3: relancez l'étape 1 sur l'entrée inversée.

Étape 4: comparer les résultats de L'Étape 1 et de l'Étape 3. Si des bits sont également espacés au-dessus et au-dessous, nous devons avoir un résultat.

gardez à l'esprit qu'aucune étape de l'algorithme ci-dessus ne prend plus de temps que O(n). ^_^

comme un avantage supplémentaire, cet algorithme trouvera tous également espacés ceux de chaque nombre. Ainsi par exemple, si vous obtenez un résultat de "0x0005" puis il y a ceux également espacés à la fois 1 et 3 unités loin

Je n'ai pas vraiment essayé d'optimiser le code ci-dessous, mais il est compilable C# code qui semble fonctionner.

using System;

namespace ThreeNumbers
{
    class Program
    {
        const int uint32Length = 32;

        static void Main(string[] args)
        {
            Console.Write("Please enter your integer: ");
            uint input = UInt32.Parse(Console.ReadLine());

            uint[] distancesLower = Distances(input);
            uint[] distancesHigher = Distances(Reverse(input));

            PrintHits(input, distancesLower, distancesHigher);
        }

        /// <summary>
        /// Returns an array showing how far the ones away from each bit in the input.  Only 
        /// considers ones at lower signifcant bits.  Index 0 represents the least significant bit 
        /// in the input.  Index 1 represents the second least significant bit in the input and so 
        /// on.  If a one is 3 away from the bit in question, then the third least significant bit 
        /// of the value will be sit.
        /// 
        /// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        public static uint[] Distances(uint input)
        {
            uint[] distanceToOnes = new uint[uint32Length];
            uint result = 0;

            //Sets how far each bit is from other ones. Going in the direction of LSB to MSB
            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                distanceToOnes[arrayIndex] = result;
                result <<= 1;

                if ((input & bitIndex) != 0)
                {
                    result |= 1;
                }
            }

            return distanceToOnes;
        }

        /// <summary>
        /// Reverses the bits in the input.
        /// 
        /// As programmed this algorithm needs O(n) time and O(n) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static uint Reverse(uint input)
        {
            uint reversedInput = 0;
            for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
            {
                reversedInput <<= 1;
                reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
            }

            return reversedInput;
        }

        /// <summary>
        /// Goes through each bit in the input, to check if there are any bits equally far away in 
        /// the distancesLower and distancesHigher
        /// </summary>
        public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
        {
            const int offset = uint32Length - 1;

            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                //hits checks if any bits are equally spaced away from our current value
                bool isBitSet = (input & bitIndex) != 0;
                uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];

                if (isBitSet && (hits != 0))
                {
                    Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
                }
            }
        }
    }
}

Quelqu'un remarquera probablement que pour un nombre suffisamment grand, les opérations en bits ne peuvent pas être effectuées en O(1). Vous auriez raison. Cependant, je conjecture que chaque solution qui utilise l'addition, la soustraction, la multiplication, ou la division (qui ne peut pas être fait en déplaçant) aurait aussi le problème.

ci-dessous est une solution. Il pourrait y avoir quelques petites erreurs ici et là, mais l'idée est bonne.

Edit: Il n'est pas n * log(n)

PSEUDO CODE:

foreach character in the string
  if the character equals 1 {         
     if length cache > 0 { //we can skip the first one
        foreach location in the cache { //last in first out kind of order
           if ((currentlocation + (currentlocation - location)) < length string)
              if (string[(currentlocation + (currentlocation - location))] equals 1)
                 return found evenly spaced string
           else
              break;
        }
     }
     remember the location of this character in a some sort of cache.
  }

return didn't find evenly spaced string

C # code:

public static Boolean FindThreeEvenlySpacedOnes(String str) {
    List<int> cache = new List<int>();

    for (var x = 0; x < str.Length; x++) {
        if (str[x] == '1') {
            if (cache.Count > 0) {
                for (var i = cache.Count - 1; i > 0; i--) {
                    if ((x + (x - cache[i])) >= str.Length)
                        break;

                    if (str[(x + (x - cache[i]))] == '1')
                        return true;                            
                }
            }
            cache.Add(x);                    
        }
    }

    return false;
}

Comment cela fonctionne:

iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache

iteration 2:
 x
 | 
101101001

iteration 3:
a x b 
| | | 
101101001
//we retrieve location a out of the cache and then based on a 
//we calculate b and check if te string contains a 1 on location b

//and of course we store x in the cache because it's a 1

iteration 4:
  axb  
  |||  
101101001

a  x  b  
|  |  |  
101101001


iteration 5:
    x  
    |  
101101001

iteration 6:
   a x b 
   | | | 
101101001

  a  x  b 
  |  |  | 
101101001
//return found evenly spaced string

évidemment, nous devons au moins vérifier les grappes de triplets en même temps, donc nous devons comprimer les vérifications d'une façon ou d'une autre. J'ai un algorithme candidat, mais l'analyse de la complexité temporelle dépasse mon seuil temporel de capacité*.

construisez un arbre où chaque noeud a trois enfants et chaque noeud contient le nombre total de 1 à ses feuilles. Construisez une liste liée sur les 1's, aussi bien. Attribuer à chaque nœud un coût proportionnel à la plage qu'elle couvre. Tant que le le temps que nous passons à chaque noeud est dans le budget, nous aurons un algorithme O(N lg n).

--

commence à la racine. Si le carré du nombre total de 1 ci-dessous, il est inférieur à son coût, appliquer l'algorithme naïf. Sinon, de manière récursive sur ses enfants.

maintenant, soit nous sommes revenus dans les limites du budget, soit nous savons qu'il n'y a pas de triplets valides entièrement contenus dans l'un des enfants. Par conséquent, nous devons vérifier l'entre-nœud triplet.

Maintenant les choses deviennent incroyablement bordélique. Nous voulons essentiellement revenir sur les ensembles potentiels d'enfants tout en limitant la gamme. Dès que la portée est suffisamment limitée pour que l'algorithme naïf tourne sous le budget, vous le faites. Profitez de la mise en œuvre, car je vous garantis que ce sera fastidieux. Il y a une dizaine de cas.

--

la raison pour laquelle je pense que l'algorithme fonctionnera est parce que les séquences sans valide les triplés semblent alterner entre les groupes de 1 et les lots de 0. Il divise effectivement l'espace de recherche à proximité, et l'arbre émule cette division.

Le temps d'exécution de l'algorithme n'est pas évident du tout. Il s'appuie sur les propriétés non triviales de la séquence. Si les 1 sont vraiment clairsemés alors l'algorithme naïf fonctionnera sous le budget. Si les 1 sont denses, alors une correspondance doit être trouvée tout de suite. Mais si la densité est "juste" (par ex. près de ~n^0,63, ce qui vous pouvez obtenir en mettant tous les bits à des positions Sans ' 2 ' chiffre dans la base 3), Je ne sais pas si cela fonctionnera. Vous devez prouver que l'effet de fractionnement est assez forte.

pas de réponse théorique ici, mais j'ai écrit un programme Java rapide pour explorer le comportement d'exécution en fonction de k et n, où n est la longueur totale de bits et k est le nombre de 1. Je suis avec quelques-uns des answerers qui disent que l'algorithme "régulier" qui vérifie toutes les paires de positions de bits et cherche le 3ème bit, même s'il faudrait O(K^2) dans le pire des cas, en réalité parce que le pire des cas nécessite des cordons de bits épars, est O(n ln n).

De toute façon, voici le programme, ci-dessous. Il s'agit d'un programme de style Monte-Carlo qui exécute un grand nombre d'essais NTRIALS pour la constante n, et génère au hasard des bitsets pour une gamme de valeurs k en utilisant des processus de Bernoulli avec une densité limitée entre des limites qui peuvent être spécifiées, et enregistre le temps d'exécution de la recherche ou l'échec de trouver un triplet de ceux également espacés, le temps mesuré par étapes pas dans le temps CPU. Je l'ai fait pour n=64, 256, 1024, 4096, 16384* (en cours d'exécution), d'abord un essai avec 500000 des essais pour voir quelles sont les valeurs de k qui prennent le plus de temps, puis un autre essai avec 5000000 essais avec des valeurs de densité réduites-focus pour voir à quoi ressemblent ces valeurs. Les temps de fonctionnement les plus longs se produisent avec une densité très faible (par exemple, pour n=4096, les pics de temps de fonctionnement sont de l'ordre de k=16-64, avec un pic faible pour la durée de fonctionnement moyenne à 4212 pas @ k=31, la durée de fonctionnement maximale étant de 5101 pas @ k=58). On dirait qu'il faudrait des valeurs extrêmement élevées de N pour que L'étape la plus défavorable de O(K^2) devienne plus grande. que L'étape O(n) où vous scannez la chaîne de bits pour trouver les indices de position du 1.

package com.example.math;

import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;

public class EvenlySpacedOnesTest {
    static public class StatisticalSummary
    {
        private int n=0;
        private double min=Double.POSITIVE_INFINITY;
        private double max=Double.NEGATIVE_INFINITY;
        private double mean=0;
        private double S=0;

        public StatisticalSummary() {}
        public void add(double x) {
            min = Math.min(min, x);
            max = Math.max(max, x);
            ++n;
            double newMean = mean + (x-mean)/n;
            S += (x-newMean)*(x-mean);
            // this algorithm for mean,std dev based on Knuth TAOCP vol 2
            mean = newMean;
        }
        public double getMax() { return (n>0)?max:Double.NaN; }
        public double getMin() { return (n>0)?min:Double.NaN; }
        public int getCount() { return n; }
        public double getMean() { return (n>0)?mean:Double.NaN; }
        public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; } 
        // some may quibble and use n-1 for sample std dev vs population std dev    
        public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
            for (int i = 0; i < statistics.length; ++i)
            {
                StatisticalSummary summary = statistics[i];
                ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
                        i,
                        summary.getCount(),
                        summary.getMin(),
                        summary.getMax(),
                        summary.getMean(),
                        summary.getStdDev());
            }
        }
    }

    public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
    {
        public void setProbability(double d);
        public boolean getNextBoolean();
    }

    static public class Bernoulli implements RandomBernoulliProcess
    {
        final private Random r = new Random();
        private double p = 0.5;
        public boolean getNextBoolean() { return r.nextDouble() < p; }
        public void setProbability(double d) { p = d; }
    }   
    static public class TestResult {
        final public int k;
        final public int nsteps;
        public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; } 
    }

    ////////////
    final private int n;
    final private int ntrials;
    final private double pmin;
    final private double pmax;
    final private Random random = new Random();
    final private Bernoulli bernoulli = new Bernoulli();
    final private BitSet bits;
    public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
        this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
        this.bits = new BitSet(n);
    }

    /*
     * generate random bit string
     */
    private int generateBits()
    {
        int k = 0; // # of 1's
        for (int i = 0; i < n; ++i)
        {
            boolean b = bernoulli.getNextBoolean();
            this.bits.set(i, b);
            if (b) ++k;
        }
        return k;
    }

    private int findEvenlySpacedOnes(int k, int[] pos) 
    {
        int[] bitPosition = new int[k];
        for (int i = 0, j = 0; i < n; ++i)
        {
            if (this.bits.get(i))
            {
                bitPosition[j++] = i;
            }
        }
        int nsteps = n; // first, it takes N operations to find the bit positions.
        boolean found = false;
        if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
        {       
            int lastBitSetPosition = bitPosition[k-1];
            for (int j1 = 0; !found && j1 < k; ++j1)
            {
                pos[0] = bitPosition[j1];
                for (int j2 = j1+1; !found && j2 < k; ++j2)
                {
                    pos[1] = bitPosition[j2];

                    ++nsteps;
                    pos[2] = 2*pos[1]-pos[0];
                    // calculate 3rd bit index that might be set;
                    // the other two indices point to bits that are set
                    if (pos[2] > lastBitSetPosition)
                        break;
                    // loop inner loop until we go out of bounds

                    found = this.bits.get(pos[2]);
                    // we're done if we find a third 1!
                }
            }
        }
        if (!found)
            pos[0]=-1;
        return nsteps;
    }

    /*
     * run an algorithm that finds evenly spaced ones and returns # of steps.
     */
    public TestResult run()
    {
        bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
        // probability of bernoulli process is randomly distributed between pmin and pmax

        // generate bit string.
        int k = generateBits();
        int[] pos = new int[3];
        int nsteps = findEvenlySpacedOnes(k, pos);
        return new TestResult(k, nsteps); 
    }

    public static void main(String[] args)
    {
        int n;
        int ntrials;
        double pmin = 0, pmax = 1;
        try {
            n = Integer.parseInt(args[0]);
            ntrials = Integer.parseInt(args[1]);
            if (args.length >= 3)
                pmin = Double.parseDouble(args[2]);
            if (args.length >= 4)
                pmax = Double.parseDouble(args[3]);
        }
        catch (Exception e)
        {
            System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
            System.exit(0);
            return; // make the compiler happy
        }

        final StatisticalSummary[] statistics;
        statistics=new StatisticalSummary[n+1];
        for (int i = 0; i <= n; ++i)
        {
            statistics[i] = new StatisticalSummary();
        }

        EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
        int printInterval=100000;
        int nextPrint = printInterval;
        for (int i = 0; i < ntrials; ++i)
        {
            TestResult result = test.run();
            statistics[result.k].add(result.nsteps);
            if (i == nextPrint)
            {
                System.err.println(i);
                nextPrint += printInterval;
            }
        }
        StatisticalSummary.printOut(System.out, statistics);
    }
}

# <algorithm>
def contains_evenly_spaced?(input)
  return false if input.size < 3
  one_indices = []
  input.each_with_index do |digit, index|
    next if digit == 0
    one_indices << index
  end
  return false if one_indices.size < 3
  previous_indexes = []
  one_indices.each do |index|
    if !previous_indexes.empty?
      previous_indexes.each do |previous_index|
        multiple = index - previous_index
        success_index = index + multiple
        return true if input[success_index] == 1
      end
    end
    previous_indexes << index
  end
  return false
end
# </algorithm>

def parse_input(input)
  input.chars.map { |c| c.to_i }
end

j'ai du mal avec les scénarios du pire avec des millions de chiffres. Fuzzing de /dev/urandom essentiellement vous donne O(n), mais je sais que le pire des cas est pire que cela. Je ne peux pas dire combien pire. Pour les petits n , il est trivial de trouver des entrées à environ 3*n*log(n) , mais il est étonnamment difficile de les différencier d'un autre ordre de croissance pour ce problème particulier.

Peut quelqu'un qui a travaillé sur le pire des cas entrées générer une chaîne de longueur supérieure à dire, cent mille?

une adaptation de L'algorithme Rabin-Karp pourrait être possible pour vous. Sa complexité est 0(n) donc il pourrait vous aider.

regardez http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

est-ce une solution? Je ne sais pas si C'est O(nlogn) mais à mon avis c'est mieux que O(n2) parce que la seule façon de ne pas trouver un triple serait une distribution de nombres premiers.

il y a place à amélioration, le second 1 pourrait être le suivant 1. Aussi aucune vérification d'erreur.

#include <iostream>

#include <string>

int findIt(std::string toCheck) {
    for (int i=0; i<toCheck.length(); i++) {
        if (toCheck[i]=='1') {
            std::cout << i << ": " << toCheck[i];
            for (int j = i+1; j<toCheck.length(); j++) {
                if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
                    std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << "    found" << std::endl;
                    return 0;
                }
            }
        }
    }
    return -1;
}

int main (int agrc, char* args[]) {
    std::string toCheck("1001011");
    findIt(toCheck);
    std::cin.get();
    return 0;
}

je pense que cet algorithme a une complexité O(N log n) (C++, DevStudio 2k5). Maintenant, je ne sais pas comment analyser un algorithme pour en déterminer la complexité, donc j'ai ajouté une métrique recueillant des informations au code. Le code compte le nombre de tests effectués sur la séquence de 1 et de 0 pour une entrée donnée (avec un peu de chance, je n'ai pas fait une boule de l'algorithme). Nous pouvons comparer le nombre réel de tests avec la valeur O et voir s'il y a une corrélation.

#include <iostream>
using namespace std;

bool HasEvenBits (string &sequence, int &num_compares)
{
  bool
    has_even_bits = false;

  num_compares = 0;

  for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
  {
    for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
    {
      ++num_compares;
      if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
      {
        has_even_bits = true;
        // we could 'break' here, but I want to know the worst case scenario so keep going to the end
      }
    }
  }

  return has_even_bits;
}

int main ()
{
  int
    count;

  string
    input = "111";

  for (int i = 3 ; i < 32 ; ++i)
  {
    HasEvenBits (input, count);
    cout << i << ", " << count << endl;
    input += "0";
  }
}

ce programme affiche le nombre de tests pour chaque longueur de chaîne jusqu'à 32 caractères. Voici les résultats:

 n  Tests  n log (n)
=====================
 3     1     1.43
 4     2     2.41
 5     4     3.49
 6     6     4.67
 7     9     5.92
 8    12     7.22
 9    16     8.59
10    20    10.00
11    25    11.46
12    30    12.95
13    36    14.48
14    42    16.05
15    49    17.64
16    56    19.27
17    64    20.92
18    72    22.59
19    81    24.30
20    90    26.02
21   100    27.77
22   110    29.53
23   121    31.32
24   132    33.13
25   144    34.95
26   156    36.79
27   169    38.65
28   182    40.52
29   196    42.41
30   210    44.31
31   225    46.23

j'ai aussi ajouté les valeurs 'n log n'. Tracez ces résultats à l'aide de l'outil graphique de votre choix pour voir une corrélation entre les deux résultats. Cette analyse s'étendre à toutes les valeurs de n? Je ne sais pas.