删数问题，贪心策略

2019年10月19日算法与设计

一、

在这里插入图片描述
思路：解：应用贪心算法设计求解
（1）设计要点
操作对象为n位高精度数，存储在数组a中。
在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。
每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。
当k=1时，在n位整数中删除哪一个数字能达到最大的目的？从左到右每相邻的两个数字比较：若出现减，即左边大于右边，则删除左边的大数字。若不出现减，即所有数字全部降序或相等，则删除左边的大数字。
当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。

二、伪代码：

在这里插入图片描述

三、源代码

==核心的是deleck函数==，main输入输出，erase删除传过来的指针所指向的数，没有什么的。
为什么不用数组，数组不能删除元素，要加很多判定条件。代码很难理解，。链表使 deleck 更接近伪代码结构。
a.size就是所剩的元素。你可以用java写，这样操作链表容易一点。

// 删数问题贪心策略.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//earase:抹去；擦除

#include <iostream>

//贪心策略：最近下降点优先
int n = 6;//位数
int k=4;//删掉的位数
//int a[n] = {1,7,8,5,4,3};//整数

typedef struct list{
	struct list* last;
	int a;
	struct list* next;
}LNode,*LinkList;


void erase(LNode *p,LinkList link) {
	LinkList  q=link;
	LNode *r;
	if (p == link) {
		if (link->next == NULL) {
			link = NULL; return;
		}
		link = p->next;
		free(q);//删除q;
	}
	if (p->next == NULL) {
		p->last->next = NULL;
		free(p);
	}
	else {
		r = p;
		r->last ->next= r->next;
		r->next->last = r->last;
		free(p);
	}
}
//源码
 void delek(LinkList link)
{
	LNode* q;
	q = link;//q指向了开头
	int m = n;
	if (k >= m) { std::cout << "全删除"; return; }
	while (k > 0) {
		for (int i = 0; (i < m - 1) &&((q->a )<= (q->next->a)); i++)
		{

			erase(q->next, link); k--; m--;

		}
	}
	while (m > 1 && link->a == 0) erase(link, link);
}

void createLinkF(LinkList * L, int a) {
LinkList p;
	p =(LinkList)malloc(sizeof(LNode));
	p->a = a;
	p->next = NULL;
	p->last = *L;
	(*L)->next = p;

}

int main()
{
	LinkList link;
	link = (LinkList)malloc(sizeof(LNode));
	link->last = NULL;
	std::cout << "n:"<<std::endl;
	std::cin >> n;//输入位数
	std::cout << "a的每位数" << std::endl;
	std::cin >> link->a;//第一位搞定先
	int y = 2; int num;
	LinkList  p = link;
	while (y <= n)
	{
		std::cin >> num;
		createLinkF(&p, num);
		p = p->next;
		y++;
	}
	std::cout << "k:" <<std::endl;
	std::cin >> k;
	//删数
	delek(link);

	LinkList e = link;
	while (e != NULL)
	{
		if (e->next != NULL) {
			std::cout << link->a << "     ";
			e = e->next;
		}
		else
		{ 
			std::cout << e->a;
			break;
		}
	}

}