Algoritmo per dividere un intervallo in intervalli e quindi trovare l'intervallo a cui appartiene un numero

Question

Algoritmo per dividere un intervallo in intervalli e quindi trovare l'intervallo a cui appartiene un numero

Naviga le tue risposte

#1 da (6 voti)
#2 da (2 voti)

6

Avere

un minimo
un massimo
numero di intervalli
un valore compreso tra minimo e massimo

Sto provando a trovare un metodo, o due, in grado di calcolare a quale intervallo appartiene il valore fornito.

Per min = 1, max = 10, numero di intervalli = 5 gli intervalli saranno [1,2], [3,4], [5,6], [7,8], [9-10]

L'altro metodo si comporterebbe come mostrato di seguito:

metodo (1) - > [1-2]
metodo (2) - > [1-2]
metodo (3) - > [3-4]
metodo (4) - > [3-4]
metodo (5) - > [5-6]
metodo (6) - > [5-6]
metodo (7) - > [7-8]
metodo (8) - > [7-8]
metodo (9) - > [9-10]
metodo (10) - > [9-10]

Questo sarebbe usato per generare una legenda per una mappa in cui la dimensione del marcatore dipende dall'intervallo a cui appartiene un valore.

Mi chiedo se esiste una buona soluzione algoritmica per questo.

I numeri con cui lavoro sono numeri interi.

Modifica:

Un altro esempio:

Per min = 1, max = 3, numero di intervalli = 2 gli intervalli sarebbero

a) [1-2], [3-3]

o

b) [1-1], [2-3]

L'altro metodo si comporterebbe come mostrato di seguito:

a)

metodo (1) - > [1-2]
metodo (2) - > [1-2]
metodo (3) - > [3-3]

o b)

metodo (1) - > [1-1]
metodo (2) - > [2-3]
metodo (3) - > [2-3]

Non ho preferenze per a) ob).

algorithms

posta tymtam 20.02.2013 - 09:04

fonte

2 risposte

Leggi altre domande sui tag algorithms

Clausole di protezione dei nomi che generano eccezioni Come proteggere il mio codice php in esecuzione su un server client?

score 6 · Answer 1

Ecco cosa farei:

Per prima cosa inizia con un array la dimensione del numero di intervalli per tenere traccia della lunghezza di ogni intervallo. Chiamiamo questo bucket_sizes[number_of_ranges]

Inizializza la dimensione di ogni bucket con la lunghezza più uniforme possibile: (max-min+1)/number_of_ranges (divisione intera)
Quindi, trova l'eccedenza che non può essere adattata in modo uniforme in ogni segmento, (max-min+1) % number_of_ranges (resto della divisione intera)
Distribuisci l'eccedenza il più uniformemente possibile tra ciascun bucket (inizia dall'indice 0, aggiungi 1 a ciascun bucket mentre sottrai 1 dall'eccedenza. Se l'indice esegue il wrapping alla fine dell'array bucket_size, inizia di nuovo dall'indice 0 e continua finché il surplus non è 0 ).

Ora che conosciamo le dimensioni di ciascun bucket, possiamo generare gli intervalli:

for (i=0, k=min; i<number_of_ranges; i++) {
  ranges[i].lo = k;
  ranges[i].hi = k+bucket_sizes[i]-1;
  k += bucket_sizes[i];
}

Per trovare l'intervallo di un numero specifico, semplicemente itera l'array ranges e abbina l'intervallo in cui ranges[i].lo <= number <= ranges[i].hi .

Ecco il codice sorgente completo che ho usato per testarlo (è scritto in C):

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

struct range
{
    int lo;
    int hi;
};

int generate_ranges(int min, int max, int number_of_ranges, struct range ranges[])
{
    int i;
    int bucket_sizes[number_of_ranges];

    int even_length = (max-min+1)/number_of_ranges;
    for(i=0; i<number_of_ranges; ++i)
        bucket_sizes[i] = even_length;

    /* distribute surplus as evenly as possible across buckets */
    int surplus = (max-min+1)%number_of_ranges;
    for(i=0; surplus>0; --surplus, i=(i+1)%number_of_ranges)
        bucket_sizes[i] += 1; 

    int n=0, k=min;
    for(i=0; i<number_of_ranges && k<=max; ++i, ++n){
        ranges[i].lo=k;
        ranges[i].hi=k+bucket_sizes[i]-1;
        k += bucket_sizes[i];
    }
    return n;
}

int number_range_index(int number, int number_of_ranges, const struct range ranges[]) {
    int i;
    for(i=0; i<number_of_ranges; ++i)
        if(number >= ranges[i].lo && number <= ranges[i].hi)
            return i;
    return number_of_ranges;
}


#define MAX_RANGES 50

int main(int argc, char *argv[]) {
    int i;
    struct range ranges[MAX_RANGES];

    if(argc != 5) {
        printf("usage: %s <min> <max> <number_of_ranges> <number>\n", argv[0]);
        return EXIT_FAILURE;
    }

    int min = atoi(argv[1]);
    int max = atoi(argv[2]);
    int number_of_ranges = atoi(argv[3]);
    int number = atoi(argv[4]);

    assert(max > min);
    assert(number >= min && number <= max);
    assert(number_of_ranges > 0);
    assert(number_of_ranges <= MAX_RANGES);

    printf("min=%d max=%d number_of_ranges=%d number=%d\n\n", min, max, number_of_ranges, number);

    int n = generate_ranges(min, max, number_of_ranges, ranges);
    for(i=0; i<number_of_ranges; i++) {
        if(i<n)
            printf("%s[%d-%d]", i>0?",":"", ranges[i].lo, ranges[i].hi);
        else
            printf("%s[]", i>0?",":"");
    }
    printf("\n\n");

    int number_idx = number_range_index(number, n, ranges);
    printf("method(%d)->[%d,%d]\n", number, ranges[number_idx].lo, ranges[number_idx].hi);

    return EXIT_SUCCESS;
}

score 2 · Answer 2

Lascia che n sia il numero di intervalli. Se puoi dividere il tuo intervallo in subranges uguali, puoi farlo in questo modo:

length_of_range = (max - min + 1) / n

For i = 1 to n:
start_of_range(i) = length_of_range * (i-1) + min  
end_of_range(i) = start_of_range(i) + length_of_range - 1   

method(number) = (number - min) / length_of_range + 1   // '/' is integer division

Se non puoi dividerli in uguali intervalli secondari, il primo% subset di(max - min + 1) % n deve avere lunghezza ((max - min + 1) / n) + 1 e il resto deve avere lunghezza (max - min + 1) / n . Sapendo questo, dovresti essere in grado di aggiustare le formule di cui sopra da solo.