Αναζήτηση μικρών διανυσμάτων σε πλέγμα 2D

Αναζήτηση μικρών διανυσμάτων σε πλέγμα 2D

Βρείτε ένα συντομότερο μη μηδενικό διάνυσμα μεταξύ ακέραιων συνδυασμών δύο βάσεων 2D μέσα σε πεπερασμένο παράθυρο.

Εισαγάγετε v1 = 2,0 και v2 = 0,3 χωρίς παρενθέσεις, με εύρος 1: -1v1 + 0v2 = (-2, 0), μήκος 2. Η αντιγραφή αντιγράφει το αριθμητικό αποτέλεσμα· η εκκαθάριση αδειάζει και τα τρία πεδία.

Κάθε διάνυσμα απαιτεί δύο ακέραιες συντεταγμένες εντός ±1000000· οι βάσεις πρέπει να είναι γραμμικά ανεξάρτητες. Διαχωρίστε με κόμματα, ελληνικά ερωτηματικά (;) ή κενά· δεκαδικά, επιστημονική γραφή και κείμενο απορρίπτονται. Ακέραιο εύρος 1–100. Ελέγχονται (2r+1)²−1 ζεύγη i,j από -r έως r εκτός (0,0), συγκρίνοντας τετράγωνα ευκλείδειων μηκών. Σε ισοπαλία μένει το πρώτο κατά αύξον i, έπειτα j. Εμφανίζεται ένα διάνυσμα, συντελεστές και μήκος με πέντε δεκαδικά, χωρίς γράφημα ή πλήρη λίστα. Μεγαλύτερο παράθυρο δεν αυξάνει το ελάχιστο, αλλά μπορεί να το αφήσει ίδιο. Μικρότερο διάνυσμα εκτός παραθύρου μπορεί να χαθεί. Πεπερασμένη απαρίθμηση 2D, χωρίς αναγωγή βάσης LLL/BKZ ή αξιολόγηση κρυπτογραφικής ασφάλειας.