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

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

Форум программистов > Центр помощи > [C++] Динамический массив

Автор: Gilgamesh 23.1.2009, 19:52

В 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");
}

Нужно изменить его так чтобы, длину каждой строки можно было вводить самому.

Автор: Shooroop 23.1.2009, 20:47

Длину какой каждой строки?? поясни.
на этапе создания или на этапе поиска??

Автор: Gilgamesh 23.1.2009, 21:02

На этапе создания.
Например чтот типо такой матрицы.
1     2   3
4     5   6   7
8     9
10 11 12 13 14

Автор: Shooroop 23.1.2009, 22:06

Код



#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");
}

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

Автор: Gilgamesh 23.1.2009, 22:35

Мда, чот алгоритм иногда не срабатывает

Автор: Shooroop 23.1.2009, 22:46

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

ща сделаю

Автор: Shooroop 24.1.2009, 00:02

Видимый массив - массив который отображается на мониторе, который мы собственно и пытаемся обрабатывать размерность(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:18

если заменить этот код:

Код


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

Автор: Gilgamesh 24.1.2009, 15:50

Спасибо