Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Java] индуктивное множество

Автор: intel 29.12.2007, 01:09

Здравствуйте, форумчане!

Есть бесконечное индуктивное множество М натуральных чисел, которое определено следующими правилами:
1. 1 Є М
2. Если x Є М, тогда 2х + 1 тоже Є М
3. Если х Є М, тогда 3х тоже Є М
4. Никакие другие елементы не пренадлежат множеству М

Вот первые семь елементов из того самого М: 1,3,7,9,15,19,21.

Метод int GetElement(int n) выдаёт n-ый елемент множества М. То биш если n равен трём, тогда результат будет равен семи.

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

Автор: LSD 29.12.2007, 13:06

Так в чем состоит задание? Написать метод getElement()?

Автор: intel 29.12.2007, 16:47

Цитата

Так в чем состоит задание? Написать метод getElement()?

Да, именно в етом. Дело в том, что я не мог "найти" оптимальный алгоритм smile

. Программа просто напросто зависала если я передовал большое значение методу GetElement(), скажем 1000000.
Но всё же мне удалось разрешить проблему smile

. Вот моё решение:

Код



public class InduktiveMenge {
      
    private int[] Menge;    
        
    public InduktiveMenge() {
        Menge = new int[1];
        Menge[0] = 1;
    }

    public int GibElement(int pos) {
        
        int a = 0; //2 * n + 1
        int b = 0; //3 * n
        int ergebnis1, ergebnis2;
        
        VergroessereArray(pos);
        for( int index = 0; index < pos; ++index ) { 
            ergebnis1 = 2 * Menge[a] + 1;         
            ergebnis2 = 3 * Menge[b];         
            if( ergebnis1 == ergebnis2 ) { 
                Menge[index + 1] = ergebnis1;
                ++a;
                ++b;
            } else if (ergebnis1 < ergebnis2) {              
                Menge[index + 1] = ergebnis1;
                ++a;
            } else {          
                Menge[index + 1] = ergebnis2;
                ++b;
            }            
        }
        return Menge[pos-1];     
    }
   
    private void VergroessereArray(int faktor) {    
        int[] kopierArray = new int[faktor + 1];       
        for (int i = 0; i < Menge.length; i++ ) {
            kopierArray[i] = Menge[i];
        }
        Menge = kopierArray;
        return;
    }
}