Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++] Динамический массив 
V
    Опции темы
Gilgamesh
Дата 23.1.2009, 19:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 23.11.2008

Репутация: нет
Всего: нет
В Microsoft Visual C++ 6.0

Задание:
В матрице A[m][n] все строки и столбцы упорядочены по неубыванию. Найти элемент массива, равный заданному числу x или сообщить о его отсутствии. Число действий в решении должно быть порядка m+n(а не порядка m*n).

Есть код
Код

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

void main()
{
    int i,j,m,n,x,mm,nn;

    printf("\n m=");
    scanf("%d", &mm);
    printf("\n n=");
    scanf("%d", &nn);

    int**a=new int*[mm];
    for(i=0;i<mm;i++){
        a[i]=new int[nn];
    }
    m=mm;
    n=nn;

    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            a[i][j]=i*n+j;
            printf("%4d",a[i][j]);
        }
        printf("\n");
    }
    printf("\n x=");
    scanf("%d",&x);
    i=0;
    m=mm;
    n=nn;

    while(i<m){
        if(a[i][n-1]==x){
            printf("\n a[%d,%d]=%d",i,n-1,x);
            m=0;
            break;
        }
        if(a[i][n-1]<x){
            i++;
            continue;
        }
        if(a[i][n-1]>x){
            n--;
            continue;
        }
    }
    if(m!=0){
        printf("\n x=%d not found",x);
    }
    printf("\n");
}


Нужно изменить его так чтобы, длину каждой строки можно было вводить самому.
PM MAIL   Вверх
Shooroop
Дата 23.1.2009, 20:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 28.4.2008
Где: Красноярск

Репутация: 2
Всего: 2
Длину какой каждой строки?? поясни.
на этапе создания или на этапе поиска??
PM MAIL ICQ   Вверх
Gilgamesh
Дата 23.1.2009, 21:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 23.11.2008

Репутация: нет
Всего: нет
На этапе создания.
Например чтот типо такой матрицы.
1     2   3  
4     5   6   7
8     9
10 11 12 13 14
PM MAIL   Вверх
Shooroop
Дата 23.1.2009, 22:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 28.4.2008
Где: Красноярск

Репутация: 2
Всего: 2
Код


#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
void main()
{
    int i,j,m,n,x,mm,nn;
    printf("\n m=");
    scanf("%d", &mm);
    printf("\n n=");
    scanf("%d", &nn);
    int**a=new int*[mm];
    for(i=0;i<mm;i++){
        a[i]=new int[nn];
    }
    m=mm;
    n=nn;
    for(i=0;i<m;i++){
        do{
            printf("line %d input n ",i);
            scanf("%d",&n);
        }while((n>nn)||(n<0));    // вводимое n не может быть больше изначальных размеров массива
        for(j=0;j<n;j++){
            a[i][j]=i*nn +j;      // здесь надо поправить в оригинале
            printf("%4d",a[i][j]);
        }
        printf("\n");
    }
    printf("\n x=");
    scanf("%d",&x);
    i=0;
    m=mm;
    n=nn;
    while(i<m && n>0){     // здесь тоже правим в оригинале
        if(a[i][n-1]==x){
            printf("\n a[%d,%d]=%d",i,n-1,x);
            m=0;
            break;
        }
        if(a[i][n-1]<x){
            i++;
            continue;
        }
        if(a[i][n-1]>x){
            n--;
            continue;
        }
    }
    if(m!=0){
        printf("\n x=%d not found",x);
    }
    printf("\n");
}

оно?? гы по моему алгоритм работать не будет

Это сообщение отредактировал(а) Shooroop - 23.1.2009, 22:33
PM MAIL ICQ   Вверх
Gilgamesh
Дата 23.1.2009, 22:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 23.11.2008

Репутация: нет
Всего: нет
Мда, чот алгоритм иногда не срабатывает
PM MAIL   Вверх
Shooroop
Дата 23.1.2009, 22:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 28.4.2008
Где: Красноярск

Репутация: 2
Всего: 2
не будет работать:
во первых задаются значения только для тех элементов массива которые входят в диапазон, в остальных будет мусорные заначения
во вторых алгоритм начинает работать с правого верхнего угла

ща сделаю
PM MAIL ICQ   Вверх
Shooroop
Дата 24.1.2009, 00:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 28.4.2008
Где: Красноярск

Репутация: 2
Всего: 2
Видимый массив - массив который отображается на мониторе, который мы собственно и пытаемся обрабатывать размерность(mm*nn), не может превышать размера фактического массива.
фактический массив - массив под который выделили память размерности (mm*(nn+1)). Состоит из 2-х частей, одномерного массива размерности (mm*1) (т.е. просто столбик) в который записываются длины строк которые мы вводим вручную и видимого массива.
получается что то типа этого:
mm=3 nn=4

3    1 2 3
1    5
4    9 10 11 12

Особенность алгоритма: в любой строке всегда должен быть первый элемент, как следствие во всем массиве всегда есть первый столбец 
Код

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

void main()
{
    int i,j,n,x,mm,nn;
    printf("\n m=");
    scanf("%d", &mm);
    printf("\n n=");
    scanf("%d", &nn);
    int**a=new int*[mm];
    for(i=0;i<mm;i++)
    {
        a[i]=new int[nn+1];
    }
    for(i=0;i<mm;i++)
    {
        do{
            printf("line %d input n ",i);
            scanf("%d",&n);
        }while((n>nn)||(n<1));
        a[i][0]=n+1;
        for(j=1;j<a[i][0];j++)
        {
            a[i][j]=i*nn+j;
            printf("%4d",a[i][j]);
        }
        printf("\n");
    }
    printf("\n x=");
    scanf("%d",&x);
    i=mm-1;
    n=1;
    bool find=false;
    while(i>=0 && n<a[i][0])
    {
        //printf("i=%d n=%d a[i][n]=%d\n",i,n,a[i][n]);
        if(a[i][n]>x) i--;
        else    
            if(a[i][n]<x) n++;
            else 
                if(a[i][n]==x)
                {
                    printf("\n a[%d,%d]=%d",i,n-1,x);
                    find=true;
                    break;
                }
    }

    if(find==false) printf("\n x=%d not found",x);
   
    printf("\n");

}


Это сообщение отредактировал(а) Shooroop - 24.1.2009, 00:23
PM MAIL ICQ   Вверх
Shooroop
Дата 24.1.2009, 00:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 28.4.2008
Где: Красноярск

Репутация: 2
Всего: 2
если заменить этот код:
Код

while(i>=0 && n<a[i][0])
    {
        if(a[i][n]>x) i--;
        else    
            if(a[i][n]<x) n++;
            else 
                if(a[i][n]==x)
                {
                    printf("\n a[%d,%d]=%d",i,n-1,x);
                    find=true;
                    break;
                }
    }

на этот:
Код

while(i>=0)
    {
        if(a[i][n]>x) i--;
        else
        {
            while(n<a[i][0])
            {
            if(a[i][n]<x) n++;
            else 
                if(a[i][n]==x)
                {
                    printf("\n a[%d,%d]=%d",i,n-1,x);
                    find=true;
                    break;
                }
            }
            break;
        }
    }

то программа будет работать быстрее(алгоритм остался прежний) т.к. выполняется меньше проверок (т.е. операторов условного перехода), если вотрешь это преподу то гарантирую оценку на бал выше и респект со стороны препода  smile 
PM MAIL ICQ   Вверх
Gilgamesh
Дата 24.1.2009, 15:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 23.11.2008

Репутация: нет
Всего: нет
Спасибо  smile 
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0754 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.