Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гаряка Асмик Статус: Специалист Рейтинг: 3381 ∙ повысить рейтинг »

lamed Статус: Бакалавр Рейтинг: 2412 ∙ повысить рейтинг »

Boriss Статус: Академик Рейтинг: 2173 ∙ повысить рейтинг »

Вопрос № 177998: Здравствуйте, уважаемые эксперты! Прошу вас помочь мне в доработке генетического алгоритма для задачи о диете: составление наиболее экономного (дешевого) рациона питания, удовлетворяющего определенным мед. Требованиям. Известен перечень доступных ...

Здравствуйте, уважаемые эксперты!
Прошу вас помочь мне в доработке генетического алгоритма для задачи о диете: составление наиболее экономного (дешевого) рациона питания, удовлетворяющего определенным мед. Требованиям. Известен перечень доступных продуктов из N наименований. Кроме того, рассматриваются такие характеристики продуктов, как витамины, минеральные вещества жиры, белки, углеводы, калорийность. Для каждого продукта известна его медицинская характеристика т.е. количественное содержание в одной единице указанных компонентов. Приемлем рацион, удовлетворяющий мед. Нормам, оптимальным является самый дешевый из них.

В моем программном коде отсутствует проверка на допустимость, то есть каждое решение (меню) должно соответствовать норме элементов в день, то есть жиров должно быть 30, углеводов 30 и тд. Стоимость же при этом должна быть минимальной. Финесс функция должна быть только для решений, удовлетворяющим нормам. То есть в выводе должна быть фитнесс функци я улучшающаяся, и оптимальное решение.
Заранее большое спасибо

#include "stdafx.h"

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>
#include <string>
using namespace
std;

#pragma hdrstop

#define MAXPOP 25


struct _Die
{
int kod; //код продукта
char Name[10];//имя продукта
float albumen;// белки
float carbo;// углеводы
float fat;// жиры
int kkal;//  Каллории
float VitaminA;// витамины
float VitaminE;// витамины
float VitaminC;// витамины
float Vitamin;// витамины
float cost;// стоимость
bool inx; //индекс использования
};

struct gene
{
int alleles[6];
 
int fitness;
float likelihood;
bool operator== (gene gn)
{
for (int i=0;i<6;i++)
{
if (gn.alleles[i] != alleles[i]) return false;
}
return true;
}
};

class SSDIE
{
public:
void File_Read();
void Gene_Menu();
void Set_inx(float, float, float, float, float,float,  int, int, int,  int, int);
int Solve();
gene GetGene(int i) { return population[i];}

_Die Die[20];
int mas_inx[6],N_Fitness,F_Fitness;
char Name_S[11][15];

protected:
int
ia,ib,ic,id,ie, ik;
int res_cost,res_al,res_ca,res_fat, res_kkal, res_VitaminA;
int result;
gene population[MAXPOP];
//вычесление процентного содержания
void (*ptrGeneralLike)(void);
void GenerateLikelihoods(void);

//fitness для каждой позиции
int (*ptrCreateFitness)(void);
int CreateFitnesses(void);


//генерация нового поколения
void CreateNewPopulation();
int GetIndex(float val);
gene Breed(int p1, int p2);
<
 br>};
//------------------------------------------------------------

void SSDIE::Set_inx(float a, float b, float c, float d, float e, float k, int af, int bf, int cf, int df, int ef)
{
ia = a; ib = b; ic = c; id = d; ie = e; ik=k;
res_al = af; res_ca = bf; res_fat = cf; res_kkal = df; res_VitaminA = ef;
}
//--генерация продуктов в меню----------------------------------
void SSDIE::Gene_Menu()
{
int idd, kod = 1,j = 0;
// 1 - фрукты, ягоды орехи
// 2 - Овощи, грибы, бахчевые
//
3 - крупы, мучное, бобовые
// 4 - молоко, молочные продукты
// 5 - мясные продукты

srand (time(NULL));
do{
idd = rand() % 20;
if((Die[idd].kod==kod) && (Die[idd].inx ==false))
{
mas_inx[j] = idd;
Die[idd].inx = true;
kod++;
j++;
}
}while(j<6);

ia = mas_inx[0];
ib = mas_inx[1];
ic = mas_inx[2];
id = mas_inx[3];
ie = mas_inx[4];
ik = mas_inx[5];
//нормы для фитнес функций
res_al = 20;     
   //белки
res_ca = 30;       //углеводы
res_fat = 30;      //жиры
res_kkal = 1500;   //каллории
res_cost = 70; //стоимость

res_VitaminA = 2;
}
//--чтение данных о продуктах из файла--------------------------------
void SSDIE::File_Read()
{
FILE *in;

char buf[255];
char *p, ps[20];

in = fopen("z:\\die.txt","rt");
if (in==NULL) {
 cout << "No file";
 _getch();
 exit (-1);
}
// чтение кода продукта
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[0],p);
//    cout<<endl<<p;
for(int i=0;i<20;i++)
{
p
= strtok(NULL, " ");
//        cout<<" "<<p;
Die[i].kod = atoi(p);
}
// чтение названия продукта
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[1],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
strcpy(Die[i].Name,p);
}
// чтение белков
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[2],p);
for(int i=0;i<20;i++)
{
p = strtok(NUL
 L, " ");
Die[i].albumen = atof(p);
}
// чтение углеводов
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[3],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].carbo = atof(p);
}
// чтение каллорий
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[4],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].kkal = atof(p);
}
// чтение жиров
fgets(buf,255,in);
p = strtok(buf,
" ");
strcpy(Name_S[5],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].fat = atof(p);
}
// чтение витамина А
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[6],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].VitaminA = atoi(p);
}
// чтение витамина E
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[7],p);
for(int i=0;
 i<20;i++)
{
p = strtok(NULL, " ");
Die[i].VitaminE = atoi(p);
}
// чтение витамина C
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[8],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].VitaminC = atoi(p);
}
// чтение витамина
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[9],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].Vitamin = atoi(p);
}
// чтение
цены
fgets(buf,255,in);
p = strtok(buf, " ");
strcpy(Name_S[10],p);
for(int i=0;i<20;i++)
{
p = strtok(NULL, " ");
Die[i].cost = atof(p);
}
fclose(in);

cout<<endl;

for(int i=0;i<20;i++) Die[i].inx = false;

}
//------------------------------------------------------------
int SSDIE::Solve()
{
int fitness = -1;
int iterations;

srand((unsigned)time(NULL));
for(int i=0;
 i<MAXPOP;i++)
{ for (int j=0;j<6;j++) population[i].alleles[j] = rand() % 201;
}

result = res_cost;
cout<<Name_S[10]<<" = "<<res_cost<<endl<<endl;
fitness = CreateFitnesses();
if (fitness != 0) return fitness;
iterations = 0;
while (fitness != 0 || iterations < 150)
{
GenerateLikelihoods();
CreateNewPopulation();
fitness = CreateFitnesses();
cin>> population[CreateFitnesses()].fitness;
if (fitness != 0)  return
fitness;
iterations++;
}
return -1;

}



//--фитнес для цены-------------------------------------------
int SSDIE::CreateFitnesses(void)
{
int fitness = 0;
for(int i=0;i<MAXPOP;i++)
{
int total = Die[ia].cost * population[i].alleles[0]/100 +
Die[ib].cost * population[i].alleles[1]/100 +
Die[ic].cost * population[i].alleles[2]/100 +
Die[id].cost * population[i].alleles[3]/100 +
Die[ie].cost * population[i].all
 eles[4]/100 +
Die[ik].cost * population[i].alleles[5]/100;


population[i].fitness = abs(total - res_cost);
fitness = popul
ation[i].fitness;
if (fitness == 0) return i;
}
return 0;
}

//------------------------------------------------------------
void SSDIE::GenerateLikelihoods(void)
{

float multinv = 0;
float like=0;

for(int i=0;i<MAXPOP;i++)
{
if(population[i].fitness==0) multinv += 1.;
else multinv += 1/((float)population[i].fitness);
}
for(int i=0;i<MAXPOP;i++)
{
if(population[i].fitness==0) like += (1. / multinv) * 100;
else like += (1/((float)population[i].fitness)
/ multinv) * 100;
population[i].likelihood = like;
}
}
//------------------------------------------------------------

void SSDIE::CreateNewPopulation()
{
gene temppop[MAXPOP];
for(int i=0;i<MAXPOP;i++)
{
int parent1 = 0, parent2 = 0, iterations = 0;
while(parent1 == parent2 || population[parent1] == population[parent2])
{
parent1 = GetIndex((float)(rand() % 201));
parent2 = GetIndex((float)(rand() % 201));
if
  (++iterations > 250) break;
}
temppop[i] = Breed(parent1, parent2);  // создание потомка
}
for(int i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
//---------------------------------------------------------------------------
int SSDIE::GetIndex(float val)
{
float last = 0;
for(int i=0;i<MAXPOP;i++)
{
if (last <= val && val <= population[i].likelihood) return i;
else last = population[i].likelihood;
}
return 4;
}
//------------------------------------------------------------
//
функция размножения - возвращает ген, который помещается во временную популяцию
gene SSDIE::Breed(int p1, int p2)
{
int crossover = rand() % 4+1;
int first = rand() % 100;

gene child = population[p1];

int initial = 0, final = 5;
if (first < 50) initial = crossover;
else final = crossover+1;

for(int i=initial;i<final;i++)
{
child.alleles[i] = population[p2].alleles[i];
if (rand() %
  101 < 7) child.alleles[i] = rand() % (result + 1);
}
return child;
}
//------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{

 setlocale (LC_ALL, "russian");
SSDIE dp;

int ans;
float summa;
//чтение данных из файла
dp.File_Read();

cout<<"Enter fitness function"<<endl;


cout<<endl;
dp.Gene_Menu();
// поиск решения
 ans = dp.Solve();
 if
(ans == -1) {
  cout << "No solution found." << endl;
 } else {
  gene gn = dp.GetGene(ans);

  for(int i=0;i<6;i++)
        cout << dp.Die[dp.mas_inx[i]].Name<<" = "<< gn.alleles[i]<< "g"<<endl;

summa = 0;
for(int i=0;i<6;i++) summa += dp.Die[dp.mas_inx[i]].cost*(float)gn.alleles[i]/100.;
cout << endl<< "Cost = "<<summa<< end
 l<< endl;
}
getch();

return 0;
}
//---------------------------------------------------------------------------

Отправлен: 23.04.2010, 14:16
Вопрос задал: Yulesik, Посетитель
Всего ответов: 1
Страница вопроса »

Приложение:
#include <iostream> #include <stdlib.h> #include <time.h> #include <conio.h> #include <stdio.h> #include <string> using namespace std; #pragma hdrstop #define MAXPOP 25 struct _Die { int kod; //код продукта char Name[10];//имя продукта float albumen;// белки float carbo;// углеводы float fat;// жиры int kkal;// Каллории float VitaminA;// витамины float VitaminE;// витамины float VitaminC;// витамины float Vitamin;// витамины float cost;// стоимость bool inx; //индекс использования }; struct gene { int alleles[6]; int fitness; float likelihood; bool operator== (gene gn) { for (int i=0;i<6;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class SSDIE { public: void File_Read(); void Gene_Menu(); void Set_inx(float, float, float, float, float,float, int, int, int, int, int); int Solve(); gene GetGene(int i) { return population[i];} _Die Die[20]; int mas_inx[6],N_Fitness,F_Fitness; char Name_S[11][15]; protected: int ia,ib,ic,id,ie, ik; int res_cost,res_al,res_ca,res_fat, res_kkal, res_VitaminA; int result; gene population[MAXPOP]; //вычесление процентного содержания void (*ptrGeneralLike)(void); void GenerateLikelihoods(void); //fitness для каждой позиции int (*ptrCreateFitness)(void); int CreateFitnesses(void); //генерация нового поколения void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; //------------------------------------------------------------ void SSDIE::Set_inx(float a, float b, float c, float d, float e, float k, int af, int bf, int cf, int df, int ef) { ia = a; ib = b; ic = c; id = d; ie = e; ik=k; res_al = af; res_ca = bf; res_fat = cf; res_kkal = df; res_VitaminA = ef; } //--генерация продуктов в меню---------------------------------- void SSDIE::Gene_Menu() { int idd, kod = 1,j = 0; // 1 - фрукты, ягоды орехи // 2 - Овощи, грибы, бахчевые // 3 - крупы, мучное, бобовые // 4 - молоко, молочные продукты // 5 - мясные продукты srand (time(NULL)); do{ idd = rand() % 20; if((Die[idd].kod==kod) && (Die[idd].inx ==false)) { mas_inx[j] = idd; Die[idd].inx = true; kod++; j++; } }while(j<6); ia = mas_inx[0]; ib = mas_inx[1]; ic = mas_inx[2]; id = mas_inx[3]; ie = mas_inx[4]; ik = mas_inx[5]; //нормы для фитнес функций res_al = 20; //белки res_ca = 30; //углеводы res_fat = 30; //жиры res_kkal = 1500; //каллории res_cost = 70; //стоимость res_VitaminA = 2; } //--чтение данных о продуктах из файла-------------------------------- void SSDIE::File_Read() { FILE *in; char buf[255]; char *p, ps[20]; in = fopen("c:\\die.txt","rt"); if (in==NULL) { cout << "No file"; _getch(); exit (-1); } // чтение кода продукта fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[0],p); // cout<<endl<<p; for(int i=0;i<20;i++) { p = strtok(NULL, " "); // cout<<" "<<p; Die[i].kod = atoi(p); } // чтение названия продукта fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[1],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); strcpy(Die[i].Name,p); } // чтение белков fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[2],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].albumen = atof(p); } // чтение углеводов fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[3],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].carbo = atof(p); } // чтение каллорий fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[4],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].kkal = atof(p); } // чтение жиров fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[5],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].fat = atof(p); } // чтение витамина А fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[6],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].VitaminA = atof(p); } // чтение витамина E fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[7],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].VitaminE = atof(p); } // чтение витамина C fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[8],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].VitaminC = atof(p); } // чтение витамина fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[9],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].Vitamin = atof(p); } // чтение цены fgets(buf,255,in); p = strtok(buf, " "); strcpy(Name_S[10],p); for(int i=0;i<20;i++) { p = strtok(NULL, " "); Die[i].cost = atof(p); } fclose(in); cout<<endl; for(int i=0;i<20;i++) Die[i].inx = false; } //------------------------------------------------------------ int SSDIE::Solve() { int fitness = -1; int iterations; srand((unsigned)time(NULL)); for(int i=0;i<MAXPOP;i++) { for (int j=0;j<6;j++) population[i].alleles[j] = rand() % 201; } result = res_cost; //cout<<Name_S[10]<<" = "<<res_cost<<endl<<endl; fitness = CreateFitnesses(); if (fitness != -1) return fitness; iterations = 0; while (true)//fitness != -1 || iterations < 200000)//150) { GenerateLikelihoods(); CreateNewPopulation(); fitness = CreateFitnesses(); //cin>> population[CreateFitnesses()].fitness; //cout << iterations << endl; if (fitness != -1) return fitness; iterations++; } return -1; } //--фитнес для цены------------------------------------------- int SSDIE::CreateFitnesses(void) { int fitness = -1; double mint, mina, minc, mink, minv, minf; int imint = -1; for(int i=0;i<MAXPOP;i++) { double total = Die[ia].cost * ((float)population[i].alleles[0]/100) + Die[ib].cost * ((float)population[i].alleles[1]/100) + Die[ic].cost * ((float)population[i].alleles[2]/100) + Die[id].cost * ((float)population[i].alleles[3]/100) + Die[ie].cost * ((float)population[i].alleles[4]/100) + Die[ik].cost * ((float)population[i].alleles[5]/100); double tal = Die[ia].albumen * ((float)population[i].alleles[0]/100) + Die[ib].albumen * ((float)population[i].alleles[1]/100) + Die[ic].albumen * ((float)population[i].alleles[2]/100) + Die[id].albumen * ((float)population[i].alleles[3]/100) + Die[ie].albumen * ((float)population[i].alleles[4]/100) + Die[ik].albumen * ((float)population[i].alleles[5]/100); double tca = Die[ia].carbo * ((float)population[i].alleles[0]/100) + Die[ib].carbo * ((float)population[i].alleles[1]/100) + Die[ic].carbo * ((float)population[i].alleles[2]/100) + Die[id].carbo * ((float)population[i].alleles[3]/100) + Die[ie].carbo * ((float)population[i].alleles[4]/100) + Die[ik].carbo * ((float)population[i].alleles[5]/100); double tkkal = Die[ia].kkal * ((float)population[i].alleles[0]/100) + Die[ib].kkal * ((float)population[i].alleles[1]/100) + Die[ic].kkal * ((float)population[i].alleles[2]/100) + Die[id].kkal * ((float)population[i].alleles[3]/100) + Die[ie].kkal * ((float)population[i].alleles[4]/100) + Die[ik].kkal * ((float)population[i].alleles[5]/100); double tvit = Die[ia].VitaminA * ((float)population[i].alleles[0]/100) + Die[ib].VitaminA * ((float)population[i].alleles[1]/100) + Die[ic].VitaminA * ((float)population[i].alleles[2]/100) + Die[id].VitaminA * ((float)population[i].alleles[3]/100) + Die[ie].VitaminA * ((float)population[i].alleles[4]/100) + Die[ik].VitaminA * ((float)population[i].alleles[5]/100); double tfat = Die[ia].fat * ((float)population[i].alleles[0]/100) + Die[ib].fat * ((float)population[i].alleles[1]/100) + Die[ic].fat * ((float)population[i].alleles[2]/100) + Die[id].fat * ((float)population[i].alleles[3]/100) + Die[ie].fat * ((float)population[i].alleles[4]/100) + Die[ik].fat * ((float)population[i].alleles[5]/100); population[i].fitness = (tfat<res_fat)||(tvit<res_VitaminA)|| (tkkal<res_kkal)||(tca<res_ca)||(tal<res_al); fitness = population[i].fitness; if (fitness == 0) { cout << "Допустимое решение (" << total << "р.): " << endl; if (imint==-1 || mint>total) { mint = total; imint = i; mina = tal; minc = tca; mink = tkkal; minv = tvit; minf = tfat; } cout << Die[ia].Name << " = " << population[i].alleles[0] << "g; "; cout << Die[ib].Name << " = " << population[i].alleles[1] << "g; "; cout << Die[ic].Name << " = " << population[i].alleles[2] << "g; "; cout << Die[id].Name << " = " << population[i].alleles[3] << "g; "; cout << Die[ie].Name << " = " << population[i].alleles[4] << "g; "; cout << Die[ik].Name << " = " << population[i].alleles[5] << "g; " << endl; } } if (imint!=-1) { cout << "fat " << minf << " vit " << minv << " kkal " << mink << " car " << minc << " al " << mina << endl; } return imint; } //------------------------------------------------------------ void SSDIE::GenerateLikelihoods(void) { float multinv = 0; float like=0; for(int i=0;i<MAXPOP;i++) { if(population[i].fitness==0) multinv += 1.; else multinv += 1/((float)population[i].fitness); } for(int i=0;i<MAXPOP;i++) { if(population[i].fitness==0) like += (1. / multinv) * 100; else like += (1/((float)population[i].fitness) / multinv) * 100; population[i].likelihood = like; } } //------------------------------------------------------------ void SSDIE::CreateNewPopulation() { gene temppop[MAXPOP]; for(int i=0;i<MAXPOP;i++) { int parent1 = 0, parent2 = 0, iterations = 0; while(parent1 == parent2 || population[parent1] == population[parent2]) { parent1 = GetIndex((float)(rand() % 201)); parent2 = GetIndex((float)(rand() % 201)); if (++iterations > 250) break; } temppop[i] = Breed(parent1, parent2); // создание потомка } for(int i=0;i<MAXPOP;i++) population[i] = temppop[i]; } //--------------------------------------------------------------------------- int SSDIE::GetIndex(float val) { float last = 0; for(int i=0;i<MAXPOP;i++) { if (last <= val && val <= population[i].likelihood) return i; else last = population[i].likelihood; } return 4; } //------------------------------------------------------------ // функция размножения - возвращает ген, который помещается во временную популяцию gene SSDIE::Breed(int p1, int p2) { int crossover = rand() % 4+1; int first = rand() % 100; gene child = population[p1]; int initial = 0, final = 5; if (first < 50) initial = crossover; else final = crossover+1; for(int i=initial;i<final;i++) { child.alleles[i] = population[p2].alleles[i]; if (rand() % 101 < 7) child.alleles[i] = rand() % (4*result + 1); } return child; } //------------------------------------------------------------ #pragma argsused int main(int argc, char* argv[]) { SSDIE dp; int ans; float summa; //чтение данных из файла dp.File_Read(); setlocale (LC_ALL, "russian"); //cout<<"Enter fitness function"<<endl; //cout<<endl; dp.Gene_Menu(); // поиск решения ans = dp.Solve(); if (ans == -1) { cout << "No solution found." << endl; } else { gene gn = dp.GetGene(ans); for(int i=0;i<6;i++) cout << dp.Die[dp.mas_inx[i]].Name<<" = "<< gn.alleles[i]<< "g"<<endl; summa = 0; for(int i=0;i<6;i++) summa += dp.Die[dp.mas_inx[i]].cost*(float)gn.alleles[i]/100.; cout << endl<< "Cost = "<<summa<< endl<< endl; } getch(); return 0; } //---------------------------------------------------------------------------
-----
Эта история - не для истории, понимаешь?

Ответ отправил: Verena, Профессионал
Ответ отправлен: 29.04.2010, 19:47
Номер ответа: 261106

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это! Как сказать этому эксперту "спасибо"?

Отправить SMS #thank 261106 на номер 1151 (Россия) | Еще номера »

Отправить WebMoney: Неплохо (30 руб.) Хорошо (40 руб.) Отлично (55 руб.) БЛЕСТЯЩЕ! (80 руб.)

Здравствуйте Уважаемые Эксперты.
Есть пример многопотоковой программы быстрой сортировки Хоара массива целых чисел.
Необходимо переделать ее для сортировки массива слов в алфавитном порядке методом Хоара.
Заранее благодарен.

Отправлен: 25.04.2010, 09:28
Вопрос задал: Мих@ил, Посетитель
Всего ответов: 1
Страница вопроса »

Приложение:
/* 178030 Есть пример многопотоковой программы быстрой сортировки Хоара массива целых чисел. Необходимо переделать ее для сортировки массива слов в алфавитном порядке. */ #include <windows.h> #include <stdlib.h> #include <time.h> #include <iostream.h> #include <conio.h> #define N 20 struct arg { int left,right; }; char* x[N]; DWORD WINAPI sort(void* p) //поток для сортировки { int l = ((arg*)p)->left, u = ((arg*)p)->right; if( l < u ) { char* temp; char* t = x[l]; int m = l; for( int i=l+1; i<=u; i++ ) if( strcmp( x[i], t ) < 0 ) { m++; temp=x[m]; x[m]=x[i]; x[i]=temp; } temp = x[l]; x[l]= x[m]; x[m]=temp; arg *r1 = new arg, *r2 = new arg; HANDLE H[2]; r1->left=l; r1->right= m-1; r2->left= m+1; r2->right = u; H[0]= CreateThread(0,0,sort, (void *)r1,0,0); H[1]= CreateThread(0,0,sort, (void *)r2,0,0); // используем WaitForMultipleObjects() вместо вызова WaitForSingleObject() в цикле WaitForMultipleObjects( 2, H, TRUE, INFINITE ); CloseHandle( H[0] ); CloseHandle( H[1] ); delete r1; delete r2; } return 1; } // вывод массива на экран void print_array( char* x[], int n ) { cout << "-----------------------------\n"; for( int i = 0; i < n; i++ ) cout << x[i] << endl; cout << "-----------------------------\n"; } void main() { srand( (unsigned)time(NULL) ); // генерируем массив случайных слов for( int i = 0; i < N; i++ ) { int len = 5 + rand()%10; // случайная длина слова от 5 символов char* p = new char[len+1]; p[len] = 0; while( len > 0 ) // генерируем случайное слово p[--len] = rand()%26 + \'a\'; x[i] = p; } cout << "\nInitial array:\n"; print_array( x, N ); arg a; a.left = 0; a.right = N-1; sort( &a ); cout << "\nSorted array:\n"; print_array( x, N ); // освобождаем память for( i = 0; i < N; i++ ) delete x[i]; cout << "Press a key to exit..."; cout.flush(); getch(); }

Ответ отправил: amnick, 9-й класс
Ответ отправлен: 26.04.2010, 15:08
Номер ответа: 261048

Оценка ответа: 5

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это! Как сказать этому эксперту "спасибо"?

Отправить SMS #thank 261048 на номер 1151 (Россия) | Еще номера »

Отправить WebMoney: Неплохо (30 руб.) Хорошо (40 руб.) Отлично (55 руб.) БЛЕСТЯЩЕ! (80 руб.)

Оценить выпуск »
Нам очень важно Ваше мнение об этом выпуске рассылки!

Задать вопрос экспертам этой рассылки »