Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.77/22: Рейтинг темы: голосов - 22, средняя оценка - 4.77
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38

Упростить цикл

18.09.2012, 10:14. Показов 4740. Ответов 36
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Хеллоу еврибади!! Дело вот в чем есть такой вот цикл:
Java
1
2
3
4
5
6
7
8
for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                flag=false;
                if(mass[j]>mass[i]){mass[i]=mass[j];flag=true; break;}
                
            }
            if (flag==false){mass[i]=0;}
        }
Он не проходит по времени выполнения, для ясности картины покажу условие всей задачи:

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 1 секунда
В массиве целых чисел необходимо заменить каждое число на другое из этого же массива, ближайшее большее по значению расположенное справа от заменяемого и большее заменяемого, или на ноль при отсутствии такового.

Формат входного файла:

В первой строке входного файла input.txt записано число - количество чисел в наборе. Во второй строке записаны сами числа через один пробел. Количество чисел в наборе не превосходит 100000. Значения всех чисел целые и по модулю не превосходят 2147483647. Гарантируется, что для предложенного набора чисел результат всегда существует. Каждая строка заканчивается переходом на новую строку.
Формат выходного файла:

В первую строку выходного файла output.txt необходимо вывести через один пробел получившиеся значения.

Пример ввода:

5
1 -2 8 3 5
Пример вывода:

8 8 0 5 0

Вот полностью рабочий код:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
 
public class zadacha1 {
    public static void main(String[] args)
    {
        int n = 0;
        int[] mass=new int[1000];
        try{
            Scanner sc = new Scanner(new File("Input.txt"));
            while(sc.hasNext()){
                n=sc.nextInt();
            for(int i=0; i<n; i++){
                mass[i]=sc.nextInt();
                
               }
            }           
            sc.close();
        }
        catch(FileNotFoundException e){}
        boolean flag=false;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                flag=false;
                if(mass[j]>mass[i]){mass[i]=mass[j];flag=true; break;}
                
            }
            if (flag==false){mass[i]=0;}
        }
        
        try{
            PrintWriter pw = new PrintWriter(new File("output.txt"));
            for(int i=0;i<n;i++){
                pw.print(mass[i]+" ");
            }
            pw.println();
            pw.close();}catch(Exception e){}
        
        
        
 
    }
}
Жду ваших предложений, всем спасибо!)
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.09.2012, 10:14
Ответы с готовыми решениями:

Цикл for вложенный в другой цикл for
Не могу разобраться с механизмом работы цикла вложенного в другой цикл. Конечный результат 499500. Никак не могу понять как получается...

Упростить цикл while
В последнем цикле while используется 2 вызова функции snake. Как сделать одиночный вызов с запоминанием результата итерации в переменную и...

Как упростить цикл?
Добрый день! Есть вот такой код: Lx = 10; Ly = 10; hx = 0.10; hy = 0.10; Nx = Lx/hx; Ny = Ly/hy; Tbf = 0; lamda_fld =...

36
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
17.10.2012, 20:23
Студворк — интернет-сервис помощи студентам
ZoRT, в моем случае количество проходов по элементам равно n+k, ровно, где n - размер массива, k - количество пиковых значений (те, которые обнуляем отдельно). В примере выше k=2 Круче оптимизировать вряд ли получится O(n) это и так победа
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
17.10.2012, 21:05
Цитата Сообщение от Psilon Посмотреть сообщение
что странного?)
да я чёт в этом месте её провтыкал, не ожидал объявления таким способом, наверное привычка к стилю легкочитаемого кода

с остальным полностью согласен


ZoRT, вариант с 3мя вложенными циклами ничего не даёт по количеству итераций, это не оптимизация, булеан или конец счётчика j оптимизация на 4 байта памяти - смешно
по поводу 100500 лишних сравнений - да верно
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
17.10.2012, 21:18
mutagen, нехорошо перменные внутри цикла объявлять, а снаружи не нужны они, поэтому так вот
0
 Аватар для Venzo
127 / 125 / 16
Регистрация: 03.07.2011
Сообщений: 354
17.10.2012, 21:22
mutagen, на счет итераций, я так не думаю.
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
17.10.2012, 22:05
Цитата Сообщение от ZoRT Посмотреть сообщение
mutagen, на счет итераций, я так не думаю.
тогда давайте добавим счётчик и вставим его в каждый цикл и посмотрим вконце
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
17.10.2012, 22:13
mutagen, есть такая штука, профайлер называется...
0
 Аватар для Venzo
127 / 125 / 16
Регистрация: 03.07.2011
Сообщений: 354
17.10.2012, 23:26
Цитата Сообщение от mutagen Посмотреть сообщение
тогда давайте добавим счётчик и вставим его в каждый цикл и посмотрим вконце
даже логически, если n = 1200, в внешнем цикле итераций будет 1200/3 = 400, а значит это минус 800 проходов внутреннего цикла. Другое дело, что внутренний цикл может сделать больше итераций, но это компенсируется.
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
17.10.2012, 23:57
Цитата Сообщение от Psilon Посмотреть сообщение
mutagen, есть такая штука, профайлер называется...
я знаю

кстати я подломал ваш алгоритм правильными данными, проверьте сами

мой там по скорости не фонтан, но зато не сбоит

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.Arrays;
import java.util.Stack;
 
public class Zadacha {
    static long start, stop;
    static int[] original = { 1, 2, 3, 4, 6, 7, 9, 1, 2, 4, 3, 6, 5, 6 };
    static int[] a;
    static int[] must =     { 2, 3, 4, 6, 7, 9, 0, 2, 4, 6, 6, 0, 6, 0 };
    static int[] b;
 
    public static void main(String[] args) {
 
        init();
        psilon(a);
 
        System.out.println("original " + Arrays.toString(original));
        System.out.println("psilon   " + Arrays.toString(a));
        System.out.println("must be  " + Arrays.toString(must));
 
        // the mutagens way
        System.out.println();
        
        init();
        mutagen(a);
 
        System.out.println("original " + Arrays.toString(original));
        System.out.println("mutagen  " + Arrays.toString(b));
        System.out.println("must be  " + Arrays.toString(must));
    }
 
    static void init() {
        a = original.clone();
    }
 
    static void shrinkStack(int pretender, Stack<Integer> stack) {
        if (stack.size() != 0 && stack.firstElement() <= pretender) {
            stack.clear();
            stack.push(pretender);
        } else {
            stack.push(pretender);
        }
    }
 
    static int compareStack(int pretender, Stack<Integer> stack) {
        for (int j = stack.size() - 1; j >= 0; j--) {
            if (pretender < stack.get(j)) {
                return stack.get(j);
            }
        }
        return 0;
    }
 
    static void mutagen(int[] a) {
        b = new int[a.length];
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(a[a.length - 1]);
        b[b.length - 1] = 0;
        for (int i = a.length - 1; i > 0; i--) {
            if (a[i - 1] < a[i]) {
                shrinkStack(a[i], stack);
//               stack.push(a[i]);
                b[i - 1] = a[i];
            } else {
                b[i - 1] = compareStack(a[i - 1], stack);
            }
        }
    }
 
    static void psilon(int[] a) {
        for (int i = a.length - 1, j; i > 0;) {
            j = i;
            for (; j > 0 && a[j - 1] < a[j]; j--) {
                a[j - 1] = a[j];
            }
            a[i] = 0;
            i = j - 1;
        }
    }
 
}
результат:

Code
1
2
3
4
5
6
7
original [1, 2, 3, 4, 6, 7, 9, 1, 2, 4, 3, 6, 5, 6]
psilon   [9, 9, 9, 9, 9, 9, 0, 6, 6, 6, 6, 0, 6, 0]
must be  [2, 3, 4, 6, 7, 9, 0, 2, 4, 6, 6, 0, 6, 0]
 
original [1, 2, 3, 4, 6, 7, 9, 1, 2, 4, 3, 6, 5, 6]
mutagen  [2, 3, 4, 6, 7, 9, 0, 2, 4, 6, 6, 0, 6, 0]
must be  [2, 3, 4, 6, 7, 9, 0, 2, 4, 6, 6, 0, 6, 0]
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
18.10.2012, 00:00
mutagen, почему? ничего не сбоит: так и задуманно.
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
18.10.2012, 00:03
Цитата Сообщение от Psilon Посмотреть сообщение
mutagen, почему? ничего не сбоит: так и задуманно.
в условиях ближайший больший справа, а не самый большой
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
18.10.2012, 00:05
mutagen, ну тогда просто надо подкорректировать) так даже проще же.
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
18.10.2012, 00:09
Цитата Сообщение от ZoRT Посмотреть сообщение
даже логически, если n = 1200, в внешнем цикле итераций будет 1200/3 = 400, а значит это минус 800 проходов внутреннего цикла. Другое дело, что внутренний цикл может сделать больше итераций, но это компенсируется.
это просто пакетная обработка по 3, разницы никакой, всё равно количество сравнений такое же как и при просто вложенных циклах, что мотать и сравнивать по одному, что мотать по 3 и сравнивать по 3,
экономия на количестве инкрементов в 3 раза, взамен индусский код

Добавлено через 42 секунды
Цитата Сообщение от Psilon Посмотреть сообщение
mutagen, ну тогда просто надо подкорректировать) так даже проще же.
жду откорректированного варианта, для сравнения
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
18.10.2012, 00:31
mutagen, а вы уверены. что поняли автора лучше меня?

Добавлено через 31 секунду
Пример ввода:

5
1 -2 8 3 5
Пример вывода:

8 8 0 5 0
почему так? Ваша программа какой выход дает?
по вашей логике должно было быть
0 8 0 5 0, но первый элемент же восьмерка. Хотя ближайшее справа меньше, а значит должен быть ноль.
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
18.10.2012, 05:05
Цитата Сообщение от OlegRuno Посмотреть сообщение
Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 1 секунда
В массиве целых чисел необходимо заменить каждое число на другое из этого же массива, ближайшее большее по значению расположенное справа от заменяемого и большее заменяемого, или на ноль при отсутствии такового.
я укладываюсь в рамки ТЗ, то что у автора в примере это может быть и ошибкой/опечаткой

Цитата Сообщение от Psilon Посмотреть сообщение
0 8 0 5 0, но первый элемент же восьмерка. Хотя ближайшее справа меньше, а значит должен быть ноль.
по моей логике
Java
1
2
3
4
5
original [1, -2, 8, 3, 5]
psilon   [8, 8, 0, 5, 0]
 
original [1, -2, 8, 3, 5]
mutagen  [8, 8, 0, 5, 0]
я просто вставил шаблон автора, всё ок

Добавлено через 3 часа 42 минуты
Psilon, я разогнал свой вариант по максимуму и жду теперь вашего

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Random;
import static java.lang.System.out;
 
public class Zadacha {
    static long start;
    static int[] original = { 1, 2, 3, 4, 6, 7, 9, 1, 2, 4, 3, 6, 5, 6 }; 
    static int[] a;
    static int[] mustBe = { 2, 3, 4, 6, 7, 9, 0, 2, 4, 6, 6, 0, 6, 0 };
 
    public static void main(String[] args) throws NoSuchMethodException, SecurityException {
 
        out.println("logic test\n");
        
        init();
        psilon();
        print("psilon");
 
        out.println();
 
        mutagen();
        print("mutagen");
 
        out.println();
 
        out.println("Timing test");
        out.println();
 
        // time test
        Random r = new Random();
        int size = 1000000;
        original = new int[size];
        for (int i = 0; i < original.length; i++) {
            original[i] = r.nextInt();
        }
 
        init();
        out.println("mutagen takes " + timeTest(Zadacha.class.getDeclaredMethod("mutagen", null)) + " ms for "
                + size + " elements");
 
        init();
        out.println("psilon takes " + timeTest(Zadacha.class.getDeclaredMethod("psilon", null)) + " ms for "
                + size + " elements");
    }
 
    static void init() {
        a = original.clone();
    }
 
    static void shrinkStack(int pretender, LinkedList<Integer> stack) {
        if (stack.getFirst() <= pretender) {
            stack.clear();
            stack.push(pretender);
        } else {
            stack.push(pretender);
        }
    }
 
    static int compareStack(int pretender, LinkedList<Integer> stack) {
        for (Integer j : stack) {
            if (pretender < j)
                return j;
        }
        return 0;
    }
 
    static void mutagen() {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        stack.push(original[original.length - 1]);
        a[a.length - 1] = 0;
        for (int i = a.length - 1; i > 0; i--) {
            if (original[i - 1] < original[i]) {
                shrinkStack(a[i], stack);
                a[i - 1] = original[i];
            } else {
                a[i - 1] = compareStack(a[i - 1], stack);
            }
        }
    }
 
    static void psilon() {
        for (int i = a.length - 1, j; i > 0;) {
            j = i;
            for (; j > 0 && a[j - 1] < a[j]; j--) {
                a[j - 1] = a[j];
            }
            a[i] = 0;
            i = j - 1;
        }
    }
 
    static void print(String who) {
        out.println("original " + Arrays.toString(original));
        out.println(String.format("%-7s  %s", who, Arrays.toString(a)));
        out.println("must be  " + Arrays.toString(mustBe));
    }
 
    static long timeTest(Method m) {
        start = System.currentTimeMillis();
        try {
            m.invoke(null, null);
        } catch (IllegalAccessException | IllegalArgumentException | InvocationTargetException e) {
            e.printStackTrace();
        }
        return System.currentTimeMillis() - start;
    }
 
}
Цитата Сообщение от Psilon Посмотреть сообщение
Хотя ближайшее справа меньше, а значит должен быть ноль.
ближайшее справа - я понимаю как большее, но ближе всего справа, а не следующее большее.
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
18.10.2012, 09:00
mutagen, извиняюсь, видимо не выспался... Буквально миллиметра не хватает, но уже настолько бесит, что не хочется этим заниматься. Алгоритм примерно тот же остается: идем с конца.
Сохраняем последнее значение следующего элемента (перед тем, как его затереть). Если следующее значение больше, чем предыдущее, то записываем это значение иначе записываем наибольшее встретившееся. Если у нас нашлось число больше, чем наше наибольшее, мы его стираем (самое первое попавшееся).
0
 Аватар для mutagen
2587 / 2260 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
18.10.2012, 10:55
Цитата Сообщение от Psilon Посмотреть сообщение
mutagen, извиняюсь, видимо не выспался... Буквально миллиметра не хватает, но уже настолько бесит, что не хочется этим заниматься. Алгоритм примерно тот же остается: идем с конца.
Сохраняем последнее значение следующего элемента (перед тем, как его затереть). Если следующее значение больше, чем предыдущее, то записываем это значение иначе записываем наибольшее встретившееся. Если у нас нашлось число больше, чем наше наибольшее, мы его стираем (самое первое попавшееся).
да нет проблем, я добрый модератор )))

у меня алгоритм такой:
все большие накапливаются в стеке если они не больше вершины, или если больше стек сжимается
если же сосед справа меньше, то тогда надо разматывать стек снизу и искать большее или 0 если конец стека

хотел бы сравнить Вашу реализации по скорости из чисто спортивного интереса, так как именно Ваша идея натолкнула меня на мысль со стеком, если Вам будет нетрудно напишите на досуге, я буду Вам признателен
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
18.10.2012, 10:57
mutagen, хорошо)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.10.2012, 10:57

Возможно ли упростить цикл?
Хотелось бы спросить можно ли избавиться от костыля в виде цикла тут: //{ qry_now.DisableControls; qry_now.First; while not...

Как упростить цикл?
Знаю, что это самая дурацкая идея. #include &lt;iostream&gt; #include &lt;iomanip&gt; using namespace std; int main() { int const...

Упростить эту часть программы, используя только один раз цикл «for»
Упростить эту часть программы, используя только один раз цикл «for» Var C, I, SM, SA, X: integer; for C := 0 to X...

Упростить простой цикл, если x становится меньшее десяти, то прибавляй один, пока x не станет больше 40
Добрый день, если возможность упростить такой цикл? while (x &lt; 10) { while...

Создать программу по всем 3 видам циклов...цикл с параметром,цикл с условием,цикл,и цикл с предусловием...
Найти сумму чисел 1 в квадрате до 10 c квадрате...операцию возведению в степень не использовать учесть особенности получения квадратного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Новые блоги и статьи
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru